Course I’m sitting in on this term (will probably have to miss two lectures, drats!):<\/p>\n
\nCSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005
\nInstructors:
\nVenkatesan Guruswami and Ryan O’Donnell
\nMeeting times: MW 10:30-11:50 at Loew Hall, Room 222
\nCourse Description
\nThe PCP Theorem states that there is a certain format for writing mathematical proofs, with the following property: a verifier can randomly spot-check only a *constant* number of bits of the proof and yet be convinced of its correctness or fallaciousness with extremely high probability. Further, proofs in this format need only be polynomially longer than they are in “classical” format, and can be produced in polynomial time from the classical proof.
\nThe proof of this theorem in the early 1990’s was a great triumph of theoretical computer science, and it became even more important in the mid-1990’s when it was shown to be extremely powerful in proving NP-hardness results for *approximate* solutions to optimization problems.
\nUnfortunately, the known proof of the PCP theorem was extremely complex and also decentralized; even complete courses devoted to it rarely finished all of the proof details. However in April 2005, Irit Dinur completely changed the PCP landscape by giving a self-contained proof taking only a dozen or so pages. (See http:\/\/eccc.uni-trier.de\/eccc-reports\/2005\/TR05-046\/index.html)
\nIn this course we will prove the PCP Theorem and also gives some of its consequences for hardness of approximation. Topics will be a mix of older work from the 1990’s, as well as very recent results on the cutting edge of research, such as:
\nInteractive proofs
\nThe Parallel Repetition Theorem
\nHardness of approximation for linear equations, clique size, maximum cut, set cover, and lattice problems
\nFourier analysis of boolean functions
\nThe Unique Games conjecture\n<\/p><\/blockquote>\nHopefully I will have time to blog about some of this, as it is probably some of the most beautiful stuff in computer science. Even if it does share a name with a drug.<\/p>\n","protected":false},"excerpt":{"rendered":"
Course I’m sitting in on this term (will probably have to miss two lectures, drats!): CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005 Instructors: Venkatesan Guruswami and Ryan O’Donnell Meeting times: MW 10:30-11:50 at Loew Hall, Room 222 Course Description The PCP Theorem states that there is a certain format for writing … <\/p>\n