Bounds on locally testable codes with unique tests

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The Unique Games Conjecture (UGC) is an important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC predicts that such PCP verifiers can have almost-perfect completeness and low-soundness. The computational complexity notion of a PCP is closely related to the combinatorial notion of a Locally Testable Code (LTC). LTCs are error-correcting codes with codeword testers that only make a constant number of queries to the tested word. All known PCP constructions use LTCs as building blocks. Furthermore, to obtain PCPs with certain properties, one usually uses LTCs with corresponding properties. In light of the strong connection between PCPs and LTCs, one may conjecture the existence of LTCs with properties similar to the ones required by the UGC. In this work we show limitations on such LTCs: We consider 2-query LTCs with codeword testers that only make unique tests. Roughly speaking, we show that any such LTC with relative distance close to 1, almost-perfect completeness and low-soundness, is of constant size. While our result does not imply anything about the correctness of the UGC, it does show some limitations of unique tests, compared, for example, to projection tests.

Original languageEnglish (US)
Title of host publicationITCS 2012 - Innovations in Theoretical Computer Science Conference
Pages190-202
Number of pages13
DOIs
StatePublished - Feb 6 2012
Externally publishedYes
Event3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, United States
Duration: Jan 8 2012Jan 10 2012

Other

Other3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012
CountryUnited States
CityCambridge, MA
Period1/8/121/10/12

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Bounds on locally testable codes with unique tests'. Together they form a unique fingerprint.

Cite this