Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PCPPs:
TR07-115 | 19th November 2007
Or Meir

Combinatorial Construction of Locally Testable Codes

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>>

TR11-073 | 3rd May 2011
Andrew Drucker

Efficient Probabilistically Checkable Debates

Probabilistically checkable debate systems (PCDSs) are debates between two competing provers, in which a polynomial-time verifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. ... more >>>

ISSN 1433-8092 | Imprint