The Taub Faculty of Computer Science Events and Talks

A Probabilistically Checkable Proof (PCP) is a proof that allows checking the validity of a statement by reading only a constant number of symbols of the proof. The PCP theorem (AS98, ALMSS98) asserts the existence of PCPs of polynomial length for any claim that can be stated as membership in an NP set. Surprisingly, all know constructions of PCPs use Locally Testable Codes (LTCs) as their combinatorial core. An LTC is an error-correcting code that has a randomized tester which reads a constant number of symbols from an input word and decides whether this word is in the code. It should accept all codewords with probability one and reject all words that are far from the code with noticeable probability. The main open question in the area of LTCs is whether there exists a family of asymptotically good LTCs. Proving the non-existence for such a family would imply that the current approach for PCP construction can not achieve linear length. In this talk I will describe a new approach to refute the existence of asymptotically good LTCs and report on progress on this problem. Time permitting, I will describe a result saying that, allowing sublinear query complexity, one can easily construct a family of LTCs with rate arbitrarily close to 1.