check
HD-Combinatorics: Special Day on "Locally testable codes" (organized by Dorit Aharonov and Noga Ron-Zewi) | Einstein Institute of Mathematics

HD-Combinatorics: Special Day on "Locally testable codes" (organized by Dorit Aharonov and Noga Ron-Zewi)

Date: 
Mon, 28/05/2018
Location: 
Eilat Hall, Feldman Building, Givat Ram
09:00 - 10:50 Noga Ron-Zewi, "Locally testable codes"

14:00 - 14:50 Dorit Aharonov, "Quantum error correcting codes"
​15:00 - 15:50 Dorit Aharonov, " Quantum Locally Testable codes and High dimensional expansion"



Abstract for Noga Ron-Zewi's talk:

Locally testable codes are error-correcting codes that admit highly efficient testing algorithms: they give a method to encode k bit messages into n bit codewords of high mutual distance such that one can check whether a codeword belongs to the code, or rather far from it, by only looking at a sub linear or even just constant number of bits of the corrupted codeword. The trade off between the rate of a code and the locality/efficiency of its testing procedure has been studied extensively in the past decade, motivated by complexity theoretic applications. In the first part of the talk, I will describe the notion of locally testable codes and its motivation. In the second part of the talk, I will survey some recent and not-so-recent results for locally testable codes. I will also highlight some of the most interesting challenges that remain.