Spatial Coupling as a Proof Technique
summary
Proves that for regular LDPC ensembles with even check degree and large fixed degrees the asymptotic conditional entropy equals the supremum of a replica symmetric functional, so the MAP threshold = potential threshold; combines interpolation bounds with spatial coupling as a proof tool to eliminate metastable minima and show BP decoding on a coupled chain reaches the optimal threshold (take L→∞ then coupling width W→∞). Presents explicit density-evolution dynamics and shows the construction works, matching predictions.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 3:34LDPC
- 7:16Phase Transitions
- 9:36Theorem
- 11:51Predictions
- 12:38First Order Phase Transition
- 13:25Inequalities
- 22:14Special Copying
- 23:01Technical Constructions
- 26:59Belief Propagation
- 30:13Belief Propagation Exit Curve
- 36:23Proof
- 42:24Special Coupling
- 42:57Main Step
- 45:54Conclusion
related talks
31mStatistical Estimation on Graphs
37mSparse Superposition Codes for the AWGN Channel, Message Passing, Replica and Spatial Coupling
01h 11mStatistical Physics and Computation in High Dimension
01h 04m"More is Different." Also in Computing?
15mSafe Couplings: Coupled Refinement Types
32mLocal Convexity Of The Tap Free Energy And Amp Convergence For Z2-Synchronization
38mAn Information Theoretic View of Hypercontractivity
19mCounterexamples to the Low-Degree Conjecture