Abstract:
We consider unconditional lower bounds in the Adaptive Massively Parallel Computation (AMPC) model introduced by Behnezhad et al. (SPAA 19), which is an adaptive variant of the Massively Parallel Computation (MPC) model. Our first contribution is an optimal lower bound on the round complexity of distinguishing whether an input graph is a cycle of length n or two cycles of length n/2. This problem, 1v2-CIRCLE, has emerged as a central problem in the study of modern massively parallel computation. We prove that any AMPC algorithm for the 1v2-CIRCLE problem with I/O capacity O(nε) per machine requires Ω(1/ε) rounds, matching the upper bound of Behnezhad et al.More generally, we develop an abstract framework for proving lower bounds in the AMPC model using techniques from Boolean function complexity. Our framework extends the polynomial method of Roughgarden et al. (JACM 18) for the MPC model in two dimensions: [o] Adaptivity, where machines can write to and adaptively read from shared memory throughout the execution of the computation. [o] Promise problems, where the algorithm only has to succeed on certain inputs. These inputs may have special structure that is of particular interest, or they may be representative of hard instances of the overall problem.
