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.