List Decoding of near optimal binary codes at Johnson Bound


Sourya Roy December 12, 2022.


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.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Improved Quantum Query Upper Bounds Based on Classical Decision Trees
  • Quantum Pseudoentanglement
  • On the Probabilistic Degree of an n-variate Boolean Function
  • Demystifying the border of depth-3 algebraic circuits
  • The Composition Complexity of Majority