Conditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
summary
Shows that MPC with linear local space is essentially equivalent to congested clique equivalence, so unconditional lower bounds would imply circuit complexity breakthroughs. Gives a conditional lower bound framework based on the one-vs-two-cycles conjecture that rules out sub-logarithmic simulations of t-round LOCAL algorithms for component-stable MPC algorithms. Demonstrates a derandomization trick using small families of 3-wise independent seeds (size ~n^3) and batched bit-reveals to deterministically find linear-size matchings in constant MPC rounds, breaking component-stability.
AI-written summary · about
chapters (9)
- 0:00MPC limitations and lower bounds
- 10:12Space regimes in MPC models
- 17:29Congested clique and linear space
- 24:39Trivial lower bounds in MPC
- 30:28One vs two cycles conjecture
- 40:37Local model simulation
- 48:49Conditional lower bounds
- 57:30Breaking component stability
- 1:00:00Summary and open challenges
related talks
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
46mDistributed Graph Techniques in the MPC Model
30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain Model
01h 02mDerandomization to Boolean Circuit Lower Bounds
01h 03mClosing Keynote Day 2
58mThe Communication Complexity Landscape of Information-theoretic MPC
58mCircuit Complexity and Connections I
01h 01mCircuit Complexity and Connections II