Theory Reading Group: PCPs and Inapproximability - Autumn 2005
PCPs and Inapproximability (with special emphasis on the Unique
Time: Wed 1:00-2:30pm
Location: TTI-C Conference Room
Organizer : (<firstname> AT tti-c DOT org)
- 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].
- 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.
- Meeting 3 (Oct 12): (1-\eps)ln n optimal hardness for
approximating SETCOVER (Presenter: Jaikumar Radhakrishnan)
Ref: [Fei, LY].
- Meeting 4 (Oct 19) UGC and Hardness of approximating
Part I: Introduction to Unique Games Conjecture (UGC) (Presenter:
Part II: UGC => Vertex-Cover is (2-\eps)-hard to approximate
(Presenter: Sourav Chakraborty)
Ref: [DS, DGKR, KR]
- Meeting 5 (Oct 26) Hardness of approximating Vertex Cover
(Contd) (Presenter: Sourav Chakraborty)
Continuation of last week's presentation.
Ref: [DS, DGKR, KR]
- Meeting 6 (Nov 2) Approximation Algorithm for MAXCUT
(Presenter: Murali Krishnan Ganapathy)
Goemans-Williamson semi-definite programming for MAXCUT
- Meeting 7 (Nov 9) UGC implies GW is optimal for MAXCUT (Presenter: Eric
Optimal Inapproximability results for MAXCUT based on the Unique Games
- Meeting 8 (Nov 16) Approximation Algorithm for Sparsest Cut (Presenter:
- Meeting 9 (Nov 23) Hardness of approximating Sparset Cut
(Presenter: Harald Räcke)
Ref: [CKKRS, KV]
- Meeting 10 (Nov 30) Approximation Algorithm for Sparsest
Cut (Contd) (Presenter: Jason Teutsch)
Continuation of presentation of Meeting 8.
Tentative Topics for future meetings
- Lattice/Code Problems
- Graph Coloring
A similar reading group organized earlier this year by Irit Dinur at the Hebrew
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
- [ARV] Sanjeev Arora, Satish Rao, Umesh
V. Vazirani: "Expander
flows, geometric embeddings and graph partitioning". STOC 2004:
- [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)
- [AS] Sanjeev Arora, Shmuel Safra: "Probabilistic
Checking of Proofs: A New Characterization of NP". J. ACM 45(1):
- [BFLS] Laszlo Babai, Lance Fortnow,
Leonid A. Levin, Mario Szegedy: "Checking
Computations in Polylogarithmic Time". STOC 1991: 21-31
- [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.
- [DGKR] Irit Dinur,
Venkatesan Guruswami, Subhash Khot, Oded Regev: "A New
Multilayered PCP and the Hardness of Hypergraph Vertex Cover",
STOC 2003: 595-601.
- [DS] Irit Dinur, Shmuel Safra "On the
Hardness of Approximating Minimum Vertex-Cover". Annals of
Mathematics, 162(1), 2005.
- [Fei] Uriel Feige: "A Threshold of ln n
for Approximating Set Cover". J. ACM 45(4): 634-652 (1998)
- [FGLSS] Uriel Feige, Shafi Goldwasser, Laszlo
Lovasz, Shmuel Safra, Mario Szegedy: "Interactive
Proofs and the Hardness of Approximating Cliques". J. ACM 43(2):
- [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)
- [Has] Johan Hastad: "Some Optimal
Inapproximability Results". J. ACM 48(4):798-859 (2001).
- [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.
- [KR] Subhash Khot, Oded Regev: "Vertex Cover
Might be Hard to Approximate to within 2-\epsilon". 379.
- [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
- [LY] Carsten Lund, Mihalis Yannakakis: "On
the Hardness of Approximating Minimization Problems". J. ACM 41(5):
- [Tre] Luca Trevisan: "Inapproximability
of Combinatorial Optimization Problems". French version
(translation by Bruno Escoffier) appeared in Optimisation Combinatiore
2, (Vangelis Paschos, Editor), Hermes, 2005.
- [Raz] Ran Raz: "A Parallel Repetition
Theorem". SIAM J. Comput. 27(3): 763-803 (1998)
This page has been accessed at least
times since Oct 1, 2005.