Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
summary
Paper proves an exact correspondence: problems solvable in LOCAL O(log n) are precisely those that are L-full, and these coincide with the Baire (descriptive combinatorics) class. Proofs use the distributed rake-and-compress decomposition to build log n perfect‑matching algorithms and the combinatorial toast (laminar finite pieces, countable extension) to build Baire solutions, leveraging Chang–Pettie techniques and Bernstein’s earlier reductions. Additional results: log* equals the Continuous class, and Borel is incomparable with randomized fast classes.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 0:47Local Model of Distributed Computing
- 2:25Local Problems on Trees
- 7:23Descriptive Combinatorics
- 11:42Bernstein
- 17:47Perfect Matching
- 24:43Continuous
- 27:17Un incomparable
- 28:17Summary
related talks
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
01h 07mComputational Complexity of Polynomial Time Problems: Introduction
29mOn disperser/lifting properties of the Index and Inner-Product functions
01h 01mCircuit Complexity and Connections II
58mExponential-Time Algorithms
23mTowards General and Tight Hardness Results for Graph Problems
56mSatisfiability Algorithms II