Speaker Name/Affiliation: Jaikumar Radhakrishnan/

TTI-Chicago/Tata Institute Mumbai

Talk Title: Gap amplification in
PCPs using lazy random walks

Date/Time: February 17 2005 at 11:00
a.m.

Coffee: 10:45 a.m.

Location: TAY 3.128

Host:

Adam Klivans

Talk Abstract:
Irit Dinur (ECCC TR05-046) gave a new
and remarkable proof of the PCP theorem using gap amplification in constra

int graphs. In a constraint graph each edge has has a constraint and one

is required to assign colors to the vertices so that the maximum number of

constraints are satisfied. The key insight in Dinur''s proof
is the def

inition and analysis of a graph powering construction
based on random w

alks. Using walks of length t in the constraint graph
G Dinur construct

s a new constraint graph G%5Et with the following
properties.

Com

pleteness: if all constraints in the original graph G can be satisfied simu

ltaneously then all constraints in G%5Et can be satisfied simultaneousl

y.

Soundness amplification: if every assignment in G leaves
an e

ps <<1/t fraction of the edges unsatisfied then every assignment in G%5Et

leaves a fraction Omega(sqrt%7Bt%7D * eps) of the constraints unsatisfied.<

br>
We present a variation of Dinur''s powering construction with better

soundness amplification: the fraction of unsatisfied constraints
is
now Omega(t*eps). The size of the new graph is roughly the
same same a

s in Dinur''s construction. The main idea is to use lazy
random walks t

hat stop with probability 1/t after each step instead
of walks of a fi

xed length t.