Upper Bound on List-decoding Radius of Binary Codes
summary
Proves a new upper bound on the list‑decoding radius for odd list sizes L≥3 and beats Blinovsky’s 1986 bound on a nontrivial rate interval, while leaving other regions unchanged; shows the Plotkin threshold jumps (e.g. for L=3 the Plotkin point sits at 5/16) and settles the slope at that point. Proof combines Kalai–Linial extraction of a sphere containing exponentially many codewords, positive semidefinite Fourier kernels (MRRW style), an Elias–Bassalygo pruning and a Ramsey reduction to a tiny highly structured subcode, yielding an explicit closed‑form corollary via a degree‑L polynomial G1 bound.
AI-written summary · about
chapters (10)
- 0:00List decoding introduction
- 3:21Bounds for list size one and two
- 6:11Plotkin point shift
- 9:01New bound for odd list sizes
- 10:51Proof technique overview
- 14:28Kalai-Linial reduction
- 20:25Positive semi-definiteness role
- 26:34Zero-centered balls packing
- 29:14Main theorem and G1 function
- 30:25Summary and open questions
related talks
01h 01mCoding for Modern Distributed Storage Systems I
01h 00mAverage-case Complexity for Polynomials, and All That
01h 17mInapproximability of Constraint Satisfaction Problems III
54mPanel Discussion
55mLower Bounds Against PC With Extension Variables
01h 37mMatrix Rigidity
01h 09mInformation Theory in Computational Complexity IV
01h 03mDecay of Correlations in Spin Systems