Grader: Omer Kadmiel
Announcements:
1.
On June 4 and June 11 the classes would be at
2.
On June 10 (Tuesday),
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-Lovász-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 error®0) 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.
The course will be on Wednesdays,
· Exercise 1, due March 5th.
· Exercise 2 (two pages), due March 26th.
· Exercise 3 (two pages), due April 16th.
Ø 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!
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,
·
A course given
by Prahladh
Harsha,
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!
|
Introduction to Probabilistically Checkable Proofs and
their connection to hardness of approximation |
Irit |
|
|
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 |
|
|
· 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 |
|
|
Self-correction of polynomials |
Dana |
|
|
Low degree testing |
Dana |
|
|
26/3/2008 |
--- |
|
|
Low degree testing and the algebraic construction (finishing the analysis of the Plane vs. Point tester and reviewing the algebraic construction) |
Dana |
|
|
Composition (PCPs of Proximity (PCPP), robust soundness, composition with PCPPs) |
Irit |
|
|
Local testing and decoding of the Hadamard code (linearity testing, the Hadamard code, local testing and decoding, quadratic functions) |
Irit |
|
|
23/4/2008 |
Passover |
--- |
|
· 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 |
|
[10:00] |
Parallel repetition: the analysis [Guest
lecture] |
|
|
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 |
|
[Tuesday |
Two query PCP with sub-constant error |
Ran Raz |
|
11/6/2008 |
Hardness of approximation and long code tests |
Irit |