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 (AroraSafra, AroraLundMotwaniSzegedySudan, 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 NPhardness of approximation problems.
In the course we will present the theorem and see the simple connection to hardness of approximation (FeigeGoldwasserLovászSafraSzegedy, 1991). Most of the course will be devoted to proofs of the theorem.
We will cover both algebraic and combinatorial techniques: low degree extension, sumcheck, selfcorrection 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 worstcase to averagecase 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 5^{th}.
· Exercise 2 (two pages), due March 26^{th}.
· Exercise 3 (two pages), due April 16^{th}.
Ø April 13: Please note corrections to Exercise 3; Thanks to Or, Yoav, Zvika and Itai for pointing out!
· Exercise 4 (two pages), due May 21^{st}. Note small correction to question 4; Thanks to Shachar for pointing out!
· Exercise 5 (two pages), due June 18^{th}. 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 BenSasson, 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 degree3 polynomial over n variables has a zero (low degree extension, the
SchwartzZippel lemma, sumcheck) 
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 

Selfcorrection 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 multiprover 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 randomnessefficient 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 subconstant error 
Ran Raz 
11/6/2008 
Hardness of approximation and long code tests 
Irit 