Coding Theory in Almost Linear Time and Sublinear Space

Explore a groundbreaking lecture on coding theory presented by Dana Moshkovitz from the University of Texas at Austin. Delve into the construction of asymptotically good error-correcting codes that can be deterministically encoded in almost linear time and sub-linear space. Discover innovative techniques for creating codes that can be deterministically decoded with similar complexity. Learn about the use of hashing in encodable codes and the application of locally correctable codes combined with a novel efficient derandomization method for decodable codes. Gain insights into this cutting-edge research, which is based on joint work with Joshua Cook from the University of Texas at Austin, as part of the "Advances in the Theory of Error-Correcting Codes" series at the Simons Institute.

Coding Theory in Almost Linear Time and Sublinear Space