Course 2: PCPs, local testing, inverse theorems




Lecture 1: (July 17): Introduction: local-to-global lifting and PCPs

Describe what is the “lifting” question, and how it is related to inverse theorems, and to PCP theorems. Define "lifting expansion" property of a high dimensional complex (in analogy with other definitions of high-dimensional expansion). Introduce lifting theorems in two studied contexts (complexes):
(1) on the complete complex.
(2) on the grassman scheme.

Lecture 2&3: (July 18,19): Lifting on the complete complex - Direct Product testing

Direct product is a basic transformation that is used often in complexity theory for “hardness amplification”. One prominent example of this is Raz’s parallel repetition theorem. The corresponding lifting question is called direct product testing and pertains to the complete complex. We will describe and prove some lifting theorems in this setting. Our goal is to show how the (optimal) expansion properties of the complete complex are used in the proof, pointing to generalizations to other expanding complexes.

Lectures 4&5: (July 20,21): Lifting on the Grassman scheme - the Raz-Safra theorem

A classical theorem of Raz and Safra (which is the heart of virtually all low-error PCP constructions) relates local consistency in a “plane vs. plane” test to global consistency. We will describe and prove the theorem, and relate it to an appropriate complex.

We will show how properties of high-dimensional expanders play a key role in parts of the proofs.

Open: Could we have inverse/lifting for bounded degree complexes? Until now this is NOT known.

Instructor: Irit Dinur