Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes

We give an efficient algorithm for list-decoding the binary code by Ta-Shma (STOC 2017) to the Johnson Bound. Ta-Shma’s code has distance $\frac{1-\varepsilon}{2}$ and rate $\Omega\left(\varepsilon^{2+o(1)}\right)$ and thus it almost achieves the Gilbert-Varshamov bound. Johnson bound states that such codes are combinatorially list decodable upto $\frac{1-\rho}{2}-$ fraction of errors as long as $\rho \geq \sqrt{\varepsilon}$. We give a polynomial time decoding algorithm that nearly achieves this bound. Thus our result implies the only known binary code that simultaneously nearly achieves both the Gilbert-Varshamov and the Johnson bounds. Our decoding algorithm is based on semidefinite programming hierarchies and includes a new rounding step which might be of independent interest.