This shows you the differences between two versions of the page.

Link to this comparison view

en:group:seminars:tmp:20050707 [2016/06/23 11:26] (current)
Line 1: Line 1:
 +---- dataentry seminar ----
 +date_dt : 2005.07.07
 +title : The PCP Theorem by gap amplification ​
 +speaker : Professor Irit Dinur
 +affiliation :  Hebrew University
 +time : 
 +room : 
 +table : seminars
 +==== abstract ====
 +Given a set of variables, and a set of local constraints over them (e.g.a 3CNF formula) define the "​satisfiability-gap"​ of the system as the smallest fraction of unsatisfiable constraints. We will describe a new proof for the PCP theorem of [AS,ALMSS] based on an iterative gap amplification step. This step is a linear-time transformation that doubles the satisfiability gap of a given system. The transformation is based on applying ``graph powering"​ to a system of constraints. It is proven via random-walk arguments, relying on expansion of the underlying graph structure. The main result can also be applied towards constructing *short* PCPs and locally-testable codes whose length is linear up to a polylog factor, and whose correctness can be probabilistically verified by making a constant number of queries. This answers an open question of Ben-Sasson et al. (STOC '​04). ​