Broadcasting on Directed Acyclic Graphs
summary
One-bit source propagates through a directed acyclic graph with edges as binary symmetric channels (IID Bernoulli δ) and nodes applying Boolean relay functions; success means the optimal error probability at layer k stays below 1/2 as k→∞. Main claims: trees obey the classic (1−2δ)^2 D>1 threshold; for random DAGs with in-degree 3 and majority gates there is a sharp phase change at threshold δ=1/6 (reconstruction for small δ with layers ≳C log k, impossible for larger δ or subexponential growth). Conjecture: 2D grids fail, 3D may succeed; AND/NAND/XOR fusion on regular grids fails.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 8:16Who cares
- 14:41Is it possible
- 16:31Intuition
- 23:31Preprocessing Decisions
- 25:21erasure channel
- 27:16theorem
- 30:26proof
related talks
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
47mSignal, if you can’t (for the damage)
31mAlgebraic Coding Problems From Quantum Fault-Tolerance
39mPolar Codes For Ids Channels
01h 03mBeyond Boolean Circuits in Garbled Circuits
35mLow-Density Parity-Check Codes And Spatial Coupling For Quantitative Group Testing
01h 07mMarrying Graph Convergence and Cascade Models
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation