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:
Homepage: http://tifr.res.in/~prahladh/teaching/2022-23/pcps

Course Announcement

Videos Problem Sets Lectures References

Online Videos of Lectures

Problem Sets

  1. PS1 [(out: 10 Feb, due: 24 Feb)]
  2. PS2 [(out: 3 Mar, due: 17 Mar)]
  3. PS3 [(out: 24 Mar, due: 7 Apr)]
  4. PS4 [(out: 14 Apr, due: 28 Apr)]

Lectures

  1. 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)
  2. 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)
  3. 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) ]
  4. 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)]
  5. 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)]
  6. 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)]
  7. 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]
  8. Hardness of approximating MAX3LIN2 (Mar 24)
    Long Code, Dictator Testing, Hardness of MAX3LIN2, Hastad's 3-bit PCP
    [Notes]; Ref: [Har10 (Lec 11)]
  9. 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]
  10. 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)]
  11. 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)]
  12. 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]

Requirements

Students taking the course for credit will be expected to:

References

[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 several times since 30 Jan, 2023.

Prahladh Harsha