Coding Theory in Almost Linear Time and Sublinear Space

Channel:

Simons Institute for the Theory of Computing

Subscribers:

68,700

Published on April 24, 2024 11:54:57 PM ● Video Link: https://www.youtube.com/watch?v=NFRRxy_XH5s

Duration: 44:24

125 views

2

Dana Moshkovitz (University of Texas at Austin)
https://simons.berkeley.edu/talks/dana-moshkovitz-university-texas-austin-2024-04-10
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).