Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 09, 2014, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Jan Hazla
I will present a paper by Dana Moshkovitz "Parallel Repetition from Fortification" (FOCS 2014).
The PCP theorem states that there exists some $\epsilon > 0$ such that it is NP-hard to distinguish between two-prover projection games with value $1$ and with value $1-\epsilon$. It can be strengthened to the following: for _every_ $\epsilon > 0$ it is NP-hard to distinguish between games with value $1$ and with value $\epsilon$.
The usual proof of the strong PCP theorem is via the parallel repetition theorem: for every game $G$ with value strictly less than $1$, there exists some $c < 1$ such that the value of the $k$-wise parallel repetition $G^k$ is at most $c^k$. However, despite substantial efforts all known proofs of the parallel repetition theorem are rather involved.
The paper shows a simpler way of proving the strong PCP theorem: given a projection game $G$, we first transform it to a "fortified" game $G'$ with the same value and then prove (easier) parallel repetition theorem for fortified games.
Automatic MiSe System Software Version 1.4803M | admin login