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 No(1)-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity on the congested clique with about N1/2 nodes, where N is the input size. We show that the average time complexity of the local computation performed at a clique node (in terms of the size of the data received by the node) in such protocols has to be substa
