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 language | English (US) |
---|---|
Title of host publication | ITCS 2012 - Innovations in Theoretical Computer Science Conference |
Pages | 190-202 |
Number of pages | 13 |
DOIs | |
State | Published - Feb 6 2012 |
Externally published | Yes |
Event | 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, United States Duration: Jan 8 2012 → Jan 10 2012 |
Other
Other | 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 |
---|---|
Country/Territory | United States |
City | Cambridge, MA |
Period | 1/8/12 → 1/10/12 |
All Science Journal Classification (ASJC) codes
- Computational Theory and Mathematics