Distributed Graph Techniques in the MPC Model
summary
Defines an MPC graph model with M machines, space per machine S, and measures rounds and total near‑linear space, then shows two concrete techniques. Round compression simulates local distributed O(log n) algorithms in O(log log n) rounds by partitioning small‑radius subgraphs (uses a max degree assumption like Δ = O(n1/9)), causing edge weights to grow and degrees to drop doubly exponentially and yielding a 2+epsilon approximation for vertex cover under the stated constraints. Random vertex sampling gives a 1+epsilon triangle estimator but requires that triangle count ≥ sqrt(average degree) (or slightly stronger with polylog overhead) and parallel repetitions for concentration.
AI-written summary · about
chapters (6)
- 0:00Introduction
- 1:01MPC model definition
- 11:55Round compression technique
- 18:26Vertex cover case study
- 31:35Constraints and lower bounds
- 35:56Triangle counting and future
related talks
01h 05mGraph Algorithms in the MPC Model
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
35mDistributed Vertex Cover Reconfiguration
35mSuperlinear Lower Bounds for Multipass Graph Processing
23mTowards General and Tight Hardness Results for Graph Problems