ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-043 | 20th May 2004 00:00

Some Applications of Coding Theory in Computational Complexity

RSS-Feed




TR04-043
Authors: Luca Trevisan
Publication: 28th May 2004 14:15
Downloads: 898
Keywords: 


Abstract:

Error-correcting codes and related combinatorial constructs
play an important role in several recent (and old) results
in computational complexity theory. In this paper we survey
results on locally-testable and locally-decodable error-correcting
codes, and their applications to complexity theory and to
cryptography.

Locally decodable codes are error-correcting codes with sub-linear
time error-correcting algorithms. They are related to private
information retrieval (a type of cryptographic protocol), and
they are used in average-case complexity and to construct
``hard-core predicates'' for one-way permutations. Locally
testable codes are error-correcting codes with sub-linear
time error-detection algorithms, and they are the combinatorial
core of probabilistically checkable proofs.



ISSN 1433-8092 | Imprint