|COMPUTER SCIENCE/DISCRETE MATH, I|
|Topic:||The PCP Theorem by Gap Amplification|
|Affiliation:||Hebrew University of Jerusalem|
|Date:||Monday, June 13|
|Time/Room:||11:15am - 12:15pm/S-101|
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 the edge 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).