A Note on Solving Problems of Substantially Super-linear Complexity in Nᵒ⁽¹⁾ Rounds of the Congested Clique

We study the possibility of designing Nᵒ⁽¹⁾-round protocols for problems of substantially super-linear polynomial-time complexity on the congested clique with about N1/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.