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

2024/05/24 by Andrzej Lingas, Lingas, Andrzej
Mathematics · Computer Science · Engineering · #Graph theory and applications #Interconnection Networks and Systems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2405.15270

Abstract

We study the possibility of designing N^o(1)-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity on the congested clique with about N^1/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 substantially larger than the time complexity of the given problem.

Related

• Towards a complexity theory for the congested clique
• Computing in a Faulty Congested Clique
• What Can We Compute in a Single Round of the Congested Clique?
• Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
• A Deterministic Algorithm for the MST Problem in Constant Rounds of\n Congested Clique