List Decoding of near optimal binary codes at Johnson Bound

Speaker

Sourya Roy December 12, 2022.

Abstract

In his breakthrough work(STOC 2017), Ta-shma gave a binary code construction which nearly matches Gilbert-Varshamov bound in terms of rate-distance tradeoff. I will describe our recent work on list decoding this code upto the popular Johnson bound radius. Our algorithm is semi-definite programming hierarchy based and at the core of our analysis is an expander mixing lemma based recursive argument. This is a joint work with Silas Richelson.