Theory Reading Group: PCPs and Inapproximability - Autumn 2005

PCPs and Inapproximability (with special emphasis on the Unique Games Conjecture)

Time: Wed 1:00-2:30pm
Location: TTI-C Conference Room
Organizer : (<firstname> AT tti-c DOT org)
Homepage: http://ttic.uchicago.edu/~prahladh/teaching/05autumn/

Reading Group Announcement

Group Meetings

  1. Meeting 1 (Sep 28): PCPs and Inapproximability - an overview (Presenter: Prahladh Harsha)
    The PCP Theorem, Raz's Parallel Repetition Theorem, Unique Games Conjecture etc.
    Ref: [ALMSS, AS, BFLS, FGLSS, Has, Raz, Tre].

  2. Meeting 2 (Oct 5): (1/2+\eps)-hardness of MAX3LIN and (7/8+\eps)-hardness of MAX3SAT (Presenter: Prahladh Harsha)
    Introduction to long code, Fourier analysis, Hastad's 3-query PCPs proving optimal hardness results for MAX3LIN and MAX3SAT.
    Ref: [Has].

  3. Meeting 3 (Oct 12): (1-\eps)ln n optimal hardness for approximating SETCOVER (Presenter: Jaikumar Radhakrishnan)
    Ref: [Fei, LY].

  4. Meeting 4 (Oct 19) UGC and Hardness of approximating Vertex-Cover
    Part I: Introduction to Unique Games Conjecture (UGC) (Presenter: Prahladh Harsha)
    Part II: UGC => Vertex-Cover is (2-\eps)-hard to approximate (Presenter: Sourav Chakraborty)
    Ref: [DS, DGKR, KR]

  5. Meeting 5 (Oct 26) Hardness of approximating Vertex Cover (Contd) (Presenter: Sourav Chakraborty)
    Continuation of last week's presentation.
    Ref: [DS, DGKR, KR]

  6. Meeting 6 (Nov 2) Approximation Algorithm for MAXCUT (Presenter: Murali Krishnan Ganapathy)
    Goemans-Williamson semi-definite programming for MAXCUT
    Ref: [GW]

  7. Meeting 7 (Nov 9) UGC implies GW is optimal for MAXCUT (Presenter: Eric Purdy)
    Optimal Inapproximability results for MAXCUT based on the Unique Games Conjecture.
    Ref: [KKMO]

  8. Meeting 8 (Nov 16) Approximation Algorithm for Sparsest Cut (Presenter: Jason Teutsch)
    Arora-Rao-Vazirani Algorithm
    Ref: [ARV]

  9. Meeting 9 (Nov 23) Hardness of approximating Sparset Cut (Presenter: Harald Räcke)
    Ref: [CKKRS, KV]

  10. Meeting 10 (Nov 30) Approximation Algorithm for Sparsest Cut (Contd) (Presenter: Jason Teutsch) New
    Continuation of presentation of Meeting 8.
    Ref: [ARV]

    Tentative Topics for future meetings

  11. Lattice/Code Problems

  12. Graph Coloring

References

A similar reading group organized earlier this year by Irit Dinur at the Hebrew University: Inapproximability Seminar (67996), Spring 2005.

The links below point to the actual location of papers at the author's homepages or other electronic repositories and the papers are not reposted locally.

  1. [ARV] Sanjeev Arora, Satish Rao, Umesh V. Vazirani: "Expander flows, geometric embeddings and graph partitioning". STOC 2004: 222-231.
  2. [ALMSS] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: "Proof Verification and the Hardness of Approximation Problems". J. ACM 45(3): 501-555 (1998)
  3. [AS] Sanjeev Arora, Shmuel Safra: "Probabilistic Checking of Proofs: A New Characterization of NP". J. ACM 45(1): 70-122 (1998)
  4. [BFLS] Laszlo Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy: "Checking Computations in Polylogarithmic Time". STOC 1991: 21-31
  5. [CKKRS] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar: "On the Hardness of Approximating Multicut and Sparsest-Cut". IEEE Conference on Computational Complexity 2005: 144-153.
  6. [DGKR] Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: "A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover", STOC 2003: 595-601.
  7. [DS] Irit Dinur, Shmuel Safra "On the Hardness of Approximating Minimum Vertex-Cover". Annals of Mathematics, 162(1), 2005.
  8. [Fei] Uriel Feige: "A Threshold of ln n for Approximating Set Cover". J. ACM 45(4): 634-652 (1998)
  9. [FGLSS] Uriel Feige, Shafi Goldwasser, Laszlo Lovasz, Shmuel Safra, Mario Szegedy: "Interactive Proofs and the Hardness of Approximating Cliques". J. ACM 43(2): 268-292 (1996).
  10. [GW] Michel X. Goemans, David P. Williamson: "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming". J. ACM 42(6): 1115-1145 (1995)
  11. [Has] Johan Hastad: "Some Optimal Inapproximability Results". J. ACM 48(4):798-859 (2001).
  12. [KKMO] Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell: "Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?" FOCS 2004: 146-154.
  13. [KR] Subhash Khot, Oded Regev: "Vertex Cover Might be Hard to Approximate to within 2-\epsilon". 379.
  14. [KV] Subhash Khot, Nisheeth Vishnoi: " The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into L1", To appear in FOCS 2005.
  15. [LY] Carsten Lund, Mihalis Yannakakis: "On the Hardness of Approximating Minimization Problems". J. ACM 41(5): 960-981 (1994).
  16. [Tre] Luca Trevisan: "Inapproximability of Combinatorial Optimization Problems". French version (translation by Bruno Escoffier) appeared in Optimisation Combinatiore 2, (Vangelis Paschos, Editor), Hermes, 2005.
  17. [Raz] Ran Raz: "A Parallel Repetition Theorem". SIAM J. Comput. 27(3): 763-803 (1998)

This page has been accessed at least several times since Oct 1, 2005.

Prahladh Harsha
Valid HTML 4.01! Valid CSS! Get Firefox!