Published On Streamed live on Apr 10, 2024
Dana Moshkovitz (University of Texas at Austin)
https://simons.berkeley.edu/talks/dan...
Advances in the Theory of Error-Correcting Codes
Typical time-efficient encoding and decoding algorithms for error correcting codes use linear space. We construct asymptotically good codes that can be deterministically encoded in almost linear time and sub-linear space, as well as asymptotically good codes that can be deterministically decoded in this complexity. The encodable codes are based on hashing. The decodable codes are based on locally correctable codes and a new efficient derandomization method.
The talk is based on joint work with Joshua Cook (University of Texas at Austin).