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

Published on ● Video Link: https://www.youtube.com/watch?v=m4jOjklIYa0



Duration: 38:45
57 views
0


Silas Richelson (UC Riverside)
https://simons.berkeley.edu/talks/silas-richelson-uc-riverside-2024-04-08
Advances in the Theory of Error-Correcting Codes

In a breakthrough result, Ta-Shma described an explicit construction of an almost optimal binary code (STOC 2017). Ta-Shma's code has distance $(1-epsilon)/2$ and rate $epsilon^{2+o(1)}$ and thus it almost achieves the Gilbert-Varshamov bound, except for the o(1) term in the exponent. The prior best list-decoding algorithm for (a variant of) Ta-Shma's code, due to Alev et al (STOC 2021), is able to recover from a $(1-\rho)/2$-fraction of errors as long as $\rho\geq2^{\log(1/\epsilon)^{1/6}}$ . In this work we give an improved analysis of a similar list-decoding algorithm. Our algorithm works for Ta-Shma's original code, and it is able to list-decode all the way to the Johnson bound: it can recover from a $(1-\rho)/2$-fraction of errors as long as $\rho\geq\sqrt{\epsilon}$ .







Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Advances in the Theory of Error-Correcting Codes
Silas Richelson