The Taub Faculty of Computer Science Events and Talks
Michael Viderman (Ph.D. Thesis Seminar)
Thursday, 02.06.2011, 14:30
Advisor: Prof. E. Ben-Sasson
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.