Probabilistically Checkable Proofs – Spring 2008


Lecturers: Irit Dinur and Dana Moshkovitz

Grader: Omer Kadmiel

 


Announcements:

1.   On June 4 and June 11 the classes would be at 10am – 1pm.

2.   On June 10 (Tuesday), 2pm – 4pm, Dana will give a talk about a new PCP result.


Course Summary

 

The Probabilistically Checkable Proofs (PCP) Theorem (Arora-Safra, Arora-Lund-Motwani-Szegedy-Sudan, 1992) states that every mathematical proof can be written in a format that allows probabilistic checking by making only a constant number of queries to the proof. The PCP theorem – not only extremely interesting by itself – was a breakthrough in proving NP-hardness of approximation problems.

 

In the course we will present the theorem and see the simple connection to hardness of approximation (Feige-Goldwasser-Lovsz-Safra-Szegedy, 1991). Most of the course will be devoted to proofs of the theorem.

We will cover both algebraic and combinatorial techniques: low degree extension, sum-check, self-correction of polynomials, low degree testing, linearity testing, quadratic testing, proof composition, parallel repetition, constraint graphs degree reduction and soundness amplification via expanders.

 

While proving PCP Theorems, we will touch upon many beautiful subjects in/related to Theoretical Computer Science, such as: codes and list decoding, locally testable and decodable codes, expanders and random walks, derandomization, program checking, property testing, polynomial identity testing and worst-case to average-case reductions. We will also introduce useful techniques: Chernoff and Chebyshev inequalities, the probabilistic method, counting and averaging, convexity, tensor product, Fourier analysis, etc.


 

The History of the PCP Theorem

 

         An illustrated history of the PCP Theorem by Ryan O'Donnell

 

 

While today we can indeed prove the basic PCP Theorem (not the PCP theorem with error0) without getting into the details of the original proof, we believe that there is much to gain from understanding the original proof in addition to the new techniques. Aside from allowing the smallest known error, the original proof is very robust and the ideas underlying it have many applications to complexity and cryptography.

 


Time & Place

 

The course will be on Wednesdays, 13:00-16:00, in Ziskind 1.

 


Exercises

 

        Exercise 1, due March 5th.

        Exercise 2 (two pages), due March 26th.

        Exercise 3 (two pages), due April 16th.

      Hints (scanned)

      April 13: Please note corrections to Exercise 3; Thanks to Or, Yoav, Zvika and Itai for pointing out!

        Exercise 4 (two pages), due May 21st. Note small correction to question 4; Thanks to Shachar for pointing out!

        Exercise 5 (two pages), due June 18th. Note the corrections to questions 2(b) and 4; Thanks to Eran and Yoav for pointing out!

 


Material Available Online

 

Proofs of the PCP Theorem:

        The original proof of the PCP Theorem: [AS92],[ALMSS92].

        Irit’s proof of the PCP Theorem: [D05]. Overview by Radhakrishnan and Sudan.

 

Courses:

        A course previously given by Uri, The Weizmann Institute.

        A course previously given by Irit, The Hebrew University.

        A course being given by Eli Ben-Sasson, Technion.

        A course given by Venkatesan Guruswami and Ryan O'Donnell, University of Washington.

        A course given by Prahladh Harsha, University of Chicago.

 


Schedule

 

If you click on the date of a class, you can download a scan of the notes. Thanks to Shachar for scanning!

Important Disclaimer: the notes are unofficial and unpolished!

 

20/2/2008

Introduction to Probabilistically Checkable Proofs and their connection to hardness of approximation

Irit

27/2/2008

Towards the proof that NP PCP[O(logn), polylogn] - Verifying that a degree-3 polynomial over n variables has a zero

(low degree extension, the Schwartz-Zippel lemma, sum-check)

 

Irit

5/3/2008

        Proof of NP PCP[O(logn), polylogn] (modulo low degree testing)

        NP PCP[O(logn), polylogn] NP PCP[O(logn), O(1)]{0,1}^polylogn

(aggregation through curves)

Irit

12/3/2008

Self-correction of polynomials

Dana

19/3/2008

Low degree testing

(starting analysis of the Plane vs. Point tester)

Dana

26/3/2008

Random Walks 2008 (Ben-Gurion University)

---

2/4/2008

Low degree testing and the algebraic construction

(finishing the analysis of the Plane vs. Point tester and reviewing the algebraic construction)

Dana

9/4/2008

Composition

(PCPs of Proximity (PCPP), robust soundness, composition with PCPPs)

Irit

16/4/2008

Local testing and decoding of the Hadamard code

(linearity testing, the Hadamard code, local testing and decoding, quadratic functions)

Irit

23/4/2008

Passover

---

30/4/2008

        NP PCPP[poly n,O(1)]

        Expanders

Irit

7/5/2008

Remembrance Day

---

14/5/2008

Perspective, Different views of PCP (as a one round multi-prover game and as a constraint graph), Parallel Repetition.

Dana

21/5/2008

[10:00]

Parallel repetition: the analysis

[Guest lecture]

Ronen Shaltiel

21/5/2008

Combinatorial proof of the PCP Theorem by randomness-efficient soundness amplification (proof structure, degree reduction)

Dana

28/5/2008

Gap Amplification analysis

Dana

4/6/2008

        Alphabet reduction

        Label cover, hardness of approximation and the Unique Games Conjecture

Irit

10/6/2008

[Tuesday 2pm]

Two query PCP with sub-constant error

Ran Raz

11/6/2008

Hardness of approximation and long code tests

Irit