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

We give an efficient algorithm for listdecoding the binary code by Ta-Shma (STOC 2017) to the Johnson Bound. Ta-Shma's code has distance 1-epsilon/2 and rate Omega(epsilon(2+o(1))) and thus it almost achieves the Gilbert-Varshamov bound. Johnson bound states that such codes are combinatorially list decodable upto 1-rho/2 - fraction of errors as long as rho >= root epsilon. 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 semi-definite programming hierarchies and includes a new rounding step which might be of independent interest.