ECCC-Report TR05-014https://eccc.weizmann.ac.il/report/2005/014Comments and Revisions published for TR05-014en-usMon, 31 Jan 2005 11:58:35 +0200
Paper TR05-014
| Short Locally Testable Codes and Proofs (Survey) |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2005/014
We survey known results regarding locally testable codes
and locally testable proofs (known as PCPs),
with emphasis on the length of these constructs.
Locally testability refers to approximately testing
large objects based on a very small number of probes,
each retrieving a single bit in the representation of the object.
This yields super-fast approximate-testing of the corresponding property
(i.e., be a codeword or a valid proof).
We also review the related concept of local decodable codes.
The currently best results regarding locally testable codes and proofs
demonstrate a trade-off between the number of probes and the length
of the code or proof (relative to the information that it encodes).
Actually, the length is always ``nearly linear'', and the trade-off
is between number of probes and the ``level of near-linearity''.
Needless to say, it is not clear whether this trade-off is inherent.
The survey consists of two independent (i.e., self-contained) parts
that cover the same material at different levels of rigor and detail.
Still, in spite of the repetitions, there may be a benefit in reading
both parts.
Mon, 31 Jan 2005 11:58:35 +0200https://eccc.weizmann.ac.il/report/2005/014