Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist
Speaker: Ran Raz , Weizmann Institute
Date: December 1 2009
Time: 4:15PM to 5:15PM
Location: 32-155
Contact: Be, 3-6098, imbe@mit.edu
Relevant URL:
The Unique Games Conjecture (UGC) is possibly the most 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 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 that such LTCs do not exist.
That is, 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.
The result intends to point out the limitations of the current
techniques for constructing PCPs. It suggests that proving the UGC may
require a new approach.
Joint work with Gillat Kol.
See other events that are part of Theory Colloquium 2009/2010
See other events happening in December 2009
