Lucky Talk: Upper Bound on List-decoding Radius of Binary Codes
summary
Claim: an upper bound on the list-decoding radius τ_L is given by an explicit function G1 of ψ0 (ψ0 = 1/2 − √(β(1−β)) from the LP1 Plotkin point), derived by reducing to a Hamming-sphere subcode and analyzing an average-radius = Bernoulli IID model per coordinate. Tools: LP (linear programming) bounds, a Plotkin-style reduction, a symmetric-subcode existence, and a minimax + Ramsey symmetrization argument. Result: odd L yields zero slope for small rates* (τ scales like √ε) while even L gives linear ε scaling.
AI-written summary · about