Open Problem: Good Locally Testable Codes - constant in all parameters

Oded's comments

The question is whether there exists locally testable codes in which all parameters are constant, where by all parameters I mean (1) the relative distance, (2) the rate, and (3) the number of queries made by the test. Recall that the test is required to always accept codewords and reject with consatnt probability any words that is at constant relative distance for the code.

Currently, one can achive constants in two of the three parameters, where the most striking result is Dinur's locally testable codes that obtain a one-over-polylogarithmic rate (by building on her short PCP, which in turn builds on work of Ben-Sasson and Sudan).

For more details, see my survey on Short Locally Testable Codes and Proofs.


Back to list of Oded's choices.