A Note on Solving Problems of Substantially Super-linear Complexity in $N^o(1)$ Rounds of the Congested Clique
<|reference_start|>A Note on Solving Problems of Substantially Super-linear Complexity in $N^o(1)$ Rounds of the Congested Clique: We study the possibility of designing $N^{o(1)}$-round protocols for problems of substantially super-linear polynomial-time complexity on the congested clique with about $N^{1/2}$ nodes, where $N$ is the input size. We show that the exponent of the polynomial (if any) bounding the average time complexity of local computations performed at a node in such protocols has to be larger than that of the polynomial bounding the time complexity of the given problem.<|reference_end|>
@article{lingas2024a,
    title={A Note on Solving Problems of Substantially Super-linear Complexity in
  $N^{o(1)}$ Rounds of the Congested Clique},
    author={Andrzej Lingas},
    journal={arXiv preprint arXiv:2405.15270},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.15270},
    primaryClass={cs.DC}
}