Equivalence classes and conditional hardness in massively parallel computations

Area of Science:

• Theoretical Computer Science
• Distributed Computing
• Algorithm Analysis

Background:

• The Massively Parallel Computation (MPC) model is crucial for large-scale data processing.
• Current MPC lower bounds rely on specific, less robust conjectures like the 'one cycle versus two cycles' problem.
• Traditional complexity theory uses more robust conjectures (e.g., P vs NP) that, if refuted, yield broad algorithmic improvements.

Purpose of the Study:

• To establish connections between MPC problems and standard complexity classes.
• To develop more robust conjectures for arguing MPC lower bounds.
• To identify problems whose hardness is equivalent to simpler conjectures.

Main Methods:

• Establishing equivalences between the class of problems solvable in sublogarithmic MPC rounds and standard space complexity classes (L and NL).
• Proving new conditional lower bounds and reductions between MPC problems.
• Introducing and analyzing new, robust conjectures for MPC lower bounds.

Main Results:

• The 'one cycle versus two cycles' conjecture is shown to be equivalent to the P conjecture.
• Refuting the P conjecture would lead to O(log log n)-round MPC algorithms for problems like list ranking, minimum cut, and planarity testing.
• Many MPC lower bounds can be argued under the even more robust P conjecture, implying O(log n)-round algorithms for problems including all-pairs shortest paths and network flow if refuted.

Conclusions:

• New, robust conjectures for MPC lower bounds are introduced, linking MPC to standard complexity classes.
• These findings provide a pathway to proving stronger lower bounds and discovering new, efficient algorithms for MPC.
• The hardness of many challenging graph problems in MPC is shown to be equivalent to simpler, more fundamental conjectures.