Time: Tues/Thurs 2:30-4:00pm (tentative)
Location: Ryerson 276 (tentative)
Organizer :
Homepage:
http://ttic.uchicago.edu/~prahladh/teaching/fall07/
The PCP theorem [AS, ALMSS] states the remarkable fact that any mathematical proof can be written in a manner such that the validity of the proof can be verified probabilistically by querying the proof only at a constant number of locations. Following the proof of this celebrated theorem and the connection between probabilistically checkable proofs (PCPs) and hardness of approximation [FGLSS] (both proved in the early 90's), this theorem was extremely powerful in proving the NP-hardness of the approximate version of several combinatorial optimization problems.
However, the early proofs of this theorem were extremely involved and very "algebraic" in nature. Recently (2005), Irit Dinur gave a remarkably simple, self-contained and "combinatorial" proof of the PCP Theorem.
In this course, we will present Dinur's proof of the PCP Theorem, a few applications of PCPs towards inapproximability results and coding theory, improved PCP constructions (short and efficient PCPs) etc. Topics covered will include a mixture of earlier and very recent work, such as:
| Prahladh Harsha |
|