A Note on Solving Problems of Substantially Super-linear Complexity in No(1) Rounds of the Congested Clique

We study the possibility of designing [Formula: see text]-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity on the congested clique with about [Formula: see text] nodes, where [Formula: see text] 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 substantially larger than the time complexity of the given problem.