Probabilistically Checkable Proofs and Gap Amplification
Speaker: Irit Dinur , Hebrew University
Date: October 26 2006
Time: 4:15PM to 5:30PM
Location: 56-114
Host: Madhu Sudan, MIT
Contact: Kevin Matulef, matulef@mit.edu
Relevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.htmlNOTE UNUSUAL DAY & PLACE
Can a proof be verified almost without reading it? The PCP theorem tells us that this can be so. Specifically, if the proof is written in the correct format (called [P]robabilistically [C]heckable [P]roof format), then it can be verified reading only a constant number of randomly chosen bits from the proof (with a decaying probability of error). This theorem is among the most important theorems in theoretical computer science. In addition to being an amazing statement about proof verification, it has far-reaching applications, especially for combinatorial optimization.
While the PCP theorem was proven in the early 90's, its initial proof was quite complex. The goal of this talk is to give a new combinatorial proof of the PCP theorem (explaining how to turn your proof into a PCP one by applying an iterative process that amplifies errors). The talk will be self-contained and include some of the background on the PCP theorem, and connections to approximation / optimization.
See other events that are part of Theory Colloquium Fall 2006
See other events happening in October 2006
