PCPs and High dimensional expanders - Fall 2016 course

Lecturer: Irit Dinur
Location: Ziskind 155
Time: Tuesday 9:15 - 11:15


Syllabus: Probabilistically checkable proofs describe a type of robustness in computation, that is higher-dimensional than error correcting codes.
An error correcting code allows recovery from a certain number of bit-errors. A PCP allows recovery from a certain number of bit errors as well as from a certain number of "edge" errors.
We will describe this high dimensionality and its relation to high dimensional expanders, which are a generalization of expander graphs.

In the first part of the course we will focus on PCPs. We will teach constructions of PCPs and show the high dimensional expansion properties that they have.
In the second part of the course we will focus on high dimensional expanders. We will study various notions of expansion and describe (the only known) construction of high dimensional expanders.

Lecture Notes:

Lecture #1 (November 8, 2016) Introduction, graph expansion, PCPs, and local tests
Lecture #2 (November 15, 2016) BLR linearity testing and "constraint expanders"
Lecture #3 (November 22, 2016) Brief intro to coding theory, low degree polynomial codes (Reed Solomon and Reed Muller), locally testable codes, and low degree tests.
Lecture #4 (November 29, 2016) Low degree tests (Rubinfeld Sudan test that queries d+2 points)
Lecture #5 (December 6, 2016) A proof of the PCP theorem with exponential size, NP \subset PCP [ poly , 1], using the quadratic functions code (QF)
Lecture #6 (December 13, 2016) Transformations on constraint systems: degree reduction, moving to an agreement testing system with two queries. (Solutions to exercise 1)
(no lecture December 20, 2016)
Lecture #7 (December 27, 2016) Expanders and random graphs, high dimensional expanders
Lecture #8 (January 3, 2017) Proof of PCP theorem (outline), gap amplification step
Lecture #9 [missing] (January 10, 2017) Alphabet reduction, end PCP theorem
Lecture #10 (January 17, 2017) Tight Hardness of Approximation: Amplification of large gaps (through parallel repetition), and the Long code
Lecture #11 [partial] (January 23, 2017) Agreement tests, direct product tests
Lecture #12 (January 30, 2017) Inbal Livni on the cube vs. cube agreement test, see this paper.
Lecture #13 (February 7, 2017) - Agreement Expansion

Homework:

Homework #1 (Due: December 6, 2016) transformations on constraint systems Note: there was an error (now corrected) in the second question - thanks to Ori and Yotam for pointing it out!

Homework #2 (Due: January 3, 2017) Expander graphs and spectral gap
Homework #3 (Due: January 17, 2017) Some high dimensional expanders (there was an error on 3.3, kudos to Yotam for noticing)

---