Next: Derandomization that is rarely
Up: Back at Weizmann (1998-2003)
Previous: On Chosen Ciphertext Security
Locally testable codes are error-correcting codes that admit
very efficient codeword tests
(i.e., involving a constant number of queries).
This work presents locally testable codes and PCPs
of almost-linear length, where almost-linear means
smaller than any constant power that is greater than 1.
Comments:
Authored by O. Goldreich and M. Sudan. Appeared in
- Proceedings of 43rd FOCS, pages 13-22, 2002.
Oded Goldreich
2003-07-30