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
Overview
Syllabus
Coding Theory in Almost Linear Time and Sublinear Space
Taught by
Simons Institute
Related Courses
-
Relaxed Local Correctability from Local Testing
-
Asymptotically-Good RLCCs with (log n)^{2+o(1)} Queries
-
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
-
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
-
Constant Query Local Decoding Against Deletions Is Impossible
-
Tree Codes - Advances in the Theory of Error-Correcting Codes
