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.
Andrzej Lingas (Mon,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: