YoVDO

Asymptotically-Good RLCCs with (log n)^{2+o(1)} Queries

Offered By: Simons Institute via YouTube

Tags

Error-Correcting Codes Courses Information Theory Courses Algorithms Courses Asymptotic Analysis Courses Computational Complexity Courses Coding Theory Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a 42-minute lecture on asymptotically-good relaxed locally correctable codes (RLCCs) with (log n)^{2+o(1)} queries, presented by Tal Yankovitz from the Weizmann Institute of Science at the Simons Institute. Delve into recent advancements in error-correcting codes, focusing on the significant milestone achieved by Kumar and Mon in constructing asymptotically good RLCCs with poly-logarithmic query complexity. Examine the intriguing question of determining the optimal value of e between 0.5 and 69 for which asymptotically-good RLCCs with query complexity (log n)^{e+o(1)} exist. Learn about the substantial progress made in narrowing this gap through the development of asymptotically-good RLCCs with a query complexity of (log n)^{2+o(1)}. Understand the key insight driving this work, which involves recognizing that strong local testability guarantees exceed the requirements for the Kumar-Mon reduction. Discover how replacing locally testable codes (LTCs) with "vanilla" expander codes possessing local testability properties near the code leads to improved results. This lecture is part of the "Advances in the Theory of Error-Correcting Codes" series and is based on joint work with Gil Cohen.

Syllabus

Asymptotically-Good RLCCs with (log n)^{2+o(1)} Queries


Taught by

Simons Institute

Related Courses

Information Theory
The Chinese University of Hong Kong via Coursera
Fundamentals of Electrical Engineering
Rice University via Coursera
Computational Neuroscience
University of Washington via Coursera
Introduction to Complexity
Santa Fe Institute via Complexity Explorer
Tutorials for Complex Systems
Santa Fe Institute via Complexity Explorer