Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Towards lower bounds on locally testable codes
event speaker icon
Michael Viderman (Ph.D. Thesis Seminar)
event date icon
Thursday, 02.06.2011, 14:30
event location icon
Taub 601
event speaker icon
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.