CSS.330.1: PCPs and Limits of approximation algorithms
- Winter/Summer Semester (2022-23)
Time: Fri 9:30-13:00 (w/ a 30 min break 11:00-11:30)
Location: A201
Instructor:
Prahladh Harsha
Homepage:
http://tifr.res.in/~prahladh/teaching/2022-23/pcps
Course Announcement
- PS1 [(out: 10 Feb, due: 24 Feb)]
- PS2 [(out: 3 Mar, due: 17 Mar)]
- PS3 [(out: 24 Mar, due: 7 Apr)]
- PS4 [(out: 14 Apr, due: 28 Apr)]
- The PCP Theorem and inapproximability of Clique (Jan 27)
Administrivia; Introduction to inapproximability; gap problems; proof checking; PCP Theorem; FGLSS reduction for inapproximability of Clique.
[Notes]; Ref: [Har10 (Lec 1-4)
- Linearity Testing and Exponential-sized constant-query PCPs (Feb 3)
BLR Linearity Testing: Coppersmith's analysis, Fourier Analysis; Exponential-sized constant-query PCPs based on linearity testing.
[Notes]; Ref: [Har10 (Lec 5-6)
- Low-Degree Testing I (Feb 10)
Introduction to low-degree testing (LDT); History of LDT; Rubinfeld-Sudan analysis of LDT; Polishchuk-Spielman analysis of Individual-degree test.
[Notes]; Ref: [RS96 (Sec 4), Spi95 (Sec 4.2) ]
- Low-Degree Testing II (Feb 17)
Polishchuk-Spielman analysis of Individual-degree test, Reed-Muller and Lifted-Reed-Solomon codes, Friedl-Sudan characterization of RM codes
[Notes]; Ref: [Spi95 (Sec 4.2) (see also BCIKS20 (Appendix D)), FS95 (Sec 2-3)]
- Low-Degree Testing III (Feb 24)
Friedl-Sudan analysis of testability of lifted-Reed-Solomon codes; PCPs from the LDT
[Notes]; Ref: [FS95 (Sec 3), Har04 (Sec 5.3-5.4)]
- PCP Composition and PCP Theorem (Mar 3)
PCP composition (PCPs of proximity, Robust PCPs), Proof of the PCP Theorem (LDT-based robust PCPP, Hadamard-based PCPP, composition)
[Notes; slides (for robust PCPP composition)]; Ref: [Har04 (Chap 3 and 5)]
- Parallel Repetition Theorem (Mar 10)
2-query PCPs, Label-cover, Parallel Repetition, Raz's theorem, Holenstein and Rao's proof of repetition theorem
[Notes]; Ref: [Har07 (Lec 11-12), Rao11]
- Hardness of approximating MAX3LIN2 (Mar 24)
Long Code, Dictator Testing, Hardness of MAX3LIN2, Hastad's 3-bit PCP
[Notes]; Ref: [Har10 (Lec 11)]
- Unique Games Conjecture and Hardness of MAXCUT (Apr 7)
Unique Games Conjecture; Majority is Stablest theorem; Khot-Kindler-Mossel-O'Donnell reduction proving UG-hardness of MAXCUT
[Notes]; Ref: [Kho02, KKMO07]
- UG-hardness of Vertex Cover and low-error LDTs (Apr 14)
Khot-Regev reformulation of UGC, UG-hardness of Vertex-Cover; Discussion on proving gap-Label-Cover with subconstant error, Improved Analysis of Low Degree Test with low soundness error
[Notes]; Ref: [Har17 (Lec 21), Har10 (Lec 7)]
- Low-error low-degree test and PCP composition (Apr 21)
Raz-Safra plane-pont test, low-error PCPs from RS LDT, 2-query PCP composition
[Notes, slides (for 2-query PCP composition)], Ref: [Har10 (Lec 7, Lec 8, Lec 9, Lec 10)]
- 2-to-2 Games Theorem: Introduction and Overview (May 3)
Introduction to 2-to-2 Games Theorem; Consequences to unique games and inapproximability; Overview of proof: Grassmann graph and its expansion
[Notes], Ref: [Kho19, KMS17]
Students taking the course for credit will be expected to:
- Do problem sets (approx 1 pset every 2-3 weeks)
- Project / Paper Presentation
- Participate actively in class
- Grading Policy:
- Problems Sets - 60%
- A total of 14 days extra-time that can be distributed across
psets
- Project / Paper Presentation -- 20%
- Class Participation -- 20%
- [BCIKS20]
- Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf:
Proximity Gaps for Reed-Solomon Codes.
FOCS 2020: 900-909 [eccc]
- [FS95]
- Katalin Friedl, Madhu Sudan:
Some Improvements to Total Degree Tests.
ISTCS 1995: 190-198 [arXiv]
- [Har04]
- Prahladh Harsha,
Robust PCPs of Proximity and Shorter PCPs, PhD Thesis, MIT 2004.
- [Har07]
- Prahladh Harsha,
CMSC 39600: PCPs, codes and inapproximability, TTI-C and UChicago, 2007.
- [Har10]
- Prahladh Harsha,
Limits of approximation algorithms: PCPs and Unique Games, TIFR and IMSc, 2010.
- [Har17]
- Prahladh Harsha,
Analysis of Boolean Functions, TIFR, 2017
- [Kho02]
- Subhash Khot, On the power of unique
2-prover 1-round games. STOC, 2002.
[ps]
- [Kho19]
- Subhash Khot, On the proof of the 2-to-2 Games Conjecture, Current Developments in Mathematics, vol 2019, pp. 43-94, 2019.
- [KMS17]
- Subhash Khot, Dor Minzer, Muli Safra: On independent sets, 2-to-2 games, and Grassmann graphs. STOC 2017: 576-589 [eccc]
- [KKMO07]
- Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell.
Optimal inapproximability results
for MAX-CUT and other 2-variable CSPs? SIAM J. Computing, 37(1):319-357, 2007.
[pdf]
- [Rao11]
- Anup Rao, Parallel Repetition in
Projection Games and a Concentration Bound. SIAM J. Comput. 40(6): 1871-1891 (2011)
[pdf]
- [RS96]
- Ronitt Rubinfeld, Madhu Sudan,
Robust Characterizations of Polynomials with Applications to Program Testing.
SIAM J. Comput. 25(2): 252-271 (1996)
[pdf]
- [Spi95]
- Daniel A. Spielman,
Computationally Efficient Error-Correcting Codes and Holographic Proofs, PhD Thesis, MIT 1995.
Previous avatars of this course: 2015, 2010, DIMACS Tutorial 2009 and 2007.
This page has been accessed at least
times since 30 Jan, 2023.