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

Fundamentals of Electrical Engineering
Rice University via Coursera
Code-Based Cryptography
Inria (French Institute for Research in Computer Science and Automation) via France Université Numerique
An Introduction to Coding Theory
Indian Institute of Technology Kanpur via Swayam
Randomized Methods in Complexity
Indian Institute of Technology Kanpur via Swayam
Introductory Concepts of Digital Computing
CEC via Swayam