Miniseries of lectures on one of the crown jewels of Theoretical Computer Science: PCP Theorem and hardness of approximation

What the PCP Theorem says is that for any NP-complete problem, such as, say, satisfiability of CNF formulas F, there is a way of constructing probabilistically checkable proofs (PCPs) \pi that can be verified superefficiently by just reading a constant number of bits (independent of the size of F). If F is satisfiable, then the proof \pi will convince us of this with probability 100%. If, however, F is not satisfiable, then after inspecting just a constant number of bits of any fake proof we will reject it with high probability. This can in turn be used to prove a wealth of strong negative results regarding the possibility of computing approximate solutions to NP-complete problems.

The lectures will be given on Thursday Nov 26 at 13:15, Tuesday Dec 1 at 10:15, Thursday Dec 3 at 13:15, Tuesday Dec 8 at 10:15, and possibly (depending on the pace of progress) Thursday Dec 10 at 13:15. We will be in seminar room 1537 on the 5th floor at Lindstedtsvägen 3. The exposition will most likely follow fairly closely that in Chapters 11 and 22 of our textbook Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak ( theory.cs.princeton.edu/complexity/ ).

More information about the course DD2445 Computational Complexity can be found at www.csc.kth.se/utbildning/kth/kurser/DD2445/kplx15/ .