Adaptive Massively Parallel Constant-round Tree Contraction
summary
Claims a constant-round AMPC algorithm for tree contraction, giving O(1/epsilon^2) rounds on trees with max degree ≤ n^epsilon and O(1/epsilon^3) rounds on general trees. It implements a preorder decomposition to contract connected groups within space bound beta, removes high-degree vertices above a threshold alpha to form a big–small tree, and uses sibling contraction plus the AMPC distributed hash table capability. Results include optimal and new constant-round AMPC routines for several tree problems and practical reversible labeling.
AI-written summary · about
chapters (6)
- 0:00Intro
- 2:43Algorithm Overview
- 7:04Adaptive massively parallel computation
- 15:58Bounded Degree Trees
- 21:28High Degree Trees
- 25:31Sibling Contraction
related talks
01h 05mGraph Algorithms in the MPC Model
46mDistributed Graph Techniques in the MPC Model
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
23mTowards General and Tight Hardness Results for Graph Problems
30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain Model
59mHardness for Graph Problems - Reductions Based on APSP and SETH