COMPUTER SCIENCE/DISCRETE MATH, I | |

Topic: | The PCP Theorem by Gap Amplification |

Speaker: | Irit Dinur |

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