List Agreement Expansion from Coboundary Expansion
summary
Claim: if a pure simplicial complex has coboundary expansion over S_l in every link and 1-up agreement expansion then list agreement testing succeeds with 3l queries under the local separation rule that any two local assignments differ on at least two vertices. Method builds a representation complex and interprets local lists as a near cover, uses the triangle test to detect bad triangles and corrects at most C·epsilon edges to obtain l global functions. Works for examples like spherical buildings.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:35Simplicial Complexes
- 4:12Agreement Testing And High Dimensional Expanders
- 5:49List Agreement Testing
- 6:31Agreement vs. List Agreement
- 8:53Near Covers
- 9:29The Triangle Test
- 10:24Coboundary Expansion
- 13:02The Representation Complex and Agreement Testing
- 13:45From Agreement to List Agreement
- 14:49The Optimistic Case: Structured Agreement
- 15:28The General Case
related talks
27mList Recovery and Local Decoding of Expander Codes
35mWhy Extension-Based Proofs Fail
25mProperty-agnostic base case extension for scalable verification of distributed systems
21mEnabling Bounded Verification of Doubly-Unbounded Distributed Agreement-Based S...
10mQuery, Communication and Discrepancy
35mSymmetry-Preserving Finite Synthesis and Amalgamation
31mCompositional Verification of Stigmergic Collective Systems
01h 03mTrustworthy Automated Reasoning