Laboratory for Foundations of Computer Science
Probabilistically Checkable Proofs and their Applications
6+ lectures given by Mary Cryan.We will focus on Probabilistically-Checkable-Proofs (PCPs) and their role in proving non-approximability results for NP-hard problems. The PCP theorem was first proved by Arora, Lund, Motwani, Sudan and Szegedy in 1995. The theorem was then used to prove many non-approximability results (for polynomial-time algorithms) for various NP-hard problems.
Over a series of lectures we will present a proof of the PCP theorem, using the recent shorter proof due to Irit Dinur. We will also cover a couple of applications of PCP. The lectures will be based on (part of) the course given by Guruswami and O'Donnell, at the University of Washington. We will use their lecture notes, available here.
Anyone interested in coming along should read the note "History of the PCP Theorem", available from the above website!
I'm planning for 6 lectures, with the expectation that we may run over a bit. At the end of the course, some of the participants may want to present a paper they are particularly interested in, and we can organise that.
Time/place
The lectures are in JCMB 2509, Monday 2pm-3pm, Friday 11am-12. We start Friday 28th April.
The first 6 lectures will take place on
28th April, 1st May, 5th May, 8th May, 12th May, 22nd May.
(I am away the week of 15th-19th May)
Syllabus
The PCP-theorem.
Applications of PCP to proving non-approximability results for NP-hard problems.
Reading
"The PCP theorem by gap amplification", by Irit Dinur. ECCC technical report TR05-046.
Scribe Notes from a course of Guruswami and O'Donnell at the University of Washington. Lectures 1-9 of CSE 533, University of Washington