## 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.