On Dinur's Proof of the PCP Theorem
Time: Fri 2016-04-01 10.15 - 14.00
Location: Room 4523, Lindstedtsvägen 5, KTH CSC
Participating: Adam Schill Collberg, Susanna F. de Rezende, Jan Elffers, and Johan Westerborn, KTH
PRACTICAL DETAILS
There will be a light lunch provided around noon to those who register at this doodle by Wednesday March 30.
ABSTRACT
Probabilistically checkable proofs are proofs that can be checked by randomized algorithms reading very few bits of the proof. In the early 1990s, it was shown that proofs for NP statements could be transformed into probabilistically checkable proofs with only a modest increase in their size. This so-called PCP theorem is considered one of the crowning achievements of theoretical computer science. The proof of this theorem was technically intricate and highly nontrivial, however. In 2005, Irit Dinur gave a dramatically simpler (and radically new) construction of probabilistically checkable proofs. In this talk, we will present Dinur's construction, closely following a survey paper by Jaikumar Radhakrishnan and Madhu Sudan ( www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01143-8/ ). We will start by explaining the notion of a probabilistically checkable proof, then present the formal definitions, and finally go through Dinur's proof in detail.