Locally Testable Codes with Constant Rate, Distance, and Locality, Part I - Irit Dinur

Explore a Computer Science/Discrete Mathematics seminar on locally testable codes with constant rate, distance, and locality. Delve into Irit Dinur's presentation from the Weizmann Institute, addressing an outstanding question in coding theory. Learn about the construction of codes based on left-right Cayley complexes, and understand their potential practical applications in efficient membership testing. Examine topics such as error correction, PCPs, high-dimensional expansion, and LDPC codes. Gain insights into the structure, definition, and parameters of these codes, as well as the algorithm used in their construction.

Intro
Locality
Local test
Best rate
C3 LTC
Constant probability
Invariance
Highdimensional expansion
Summary
Main result
Symmetrical
Outline
LDPC
Code
Expander codes
Dual codes
Graph with squares
Structure
Code definition
Intermediate code
Algorithm
Recap
Parameters