EPFL

Algo+LMA

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

— |
en:group:seminars: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 | ||

+ | =================== | ||

+ | template:datatemplates:seminar | ||

+ | ----------------------- | ||

+ | |||

+ | |||

+ | ==== 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). | ||