Search papers, labs, and topics across Lattice.
This paper investigates the limitations of Massively Parallel Computation (MPC) for solving problems with super-linear time complexity in a sub-logarithmic number of rounds. The authors prove a lower bound on the local computation time required by each machine in the MPC model, showing it must exceed the exponent of the original problem's time complexity. This result holds when machines have limited local memory and their number is capped at the input size.
Sub-logarithmic MPC protocols for super-linear problems are fundamentally limited: you can't cheat time complexity without paying a steep price in local computation.
We study the possibility of designing $N^{o(1)}$-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity in the model of Massively Parallel Computation, where $N$ is the input size. We show that if the machines are not equipped with relatively large local memory and their number does not exceed $N$, then the exponent of the average time complexity of the local computation performed by a machine in a round (in terms of local memory size) in such protocols must be larger than the exponent of the time complexity of the given problem.
