Princeton University Computer Science Department

Computer Science 598B Seminar in Algorithms and Complexity  Sanjeev Arora

Spring 2005

Course Summary

This seminar course will focus on a few topics of current interest in theoretical computer science.

1.  Geometric embeddings of finite metric spaces, which has led to several breakthroughs in recent years, including new approximation algorithms for several NP-hard optimization problems.
2. Nonconstructive methods in theoretical CS and combinatorics. This is not a well-established area and we will map out current knowledge. Our investigation is ultimately motivated by the failure of the research effort to separate P and NP , and the related failure to prove good circuit lowerbounds. Work by Razborov and Rudich on Natural Proofs in 1994 ---which will also be presented in the seminar--- suggested nonconstructive methods might prove useful.
3. Efficient algorithms for geometric optimization problems, including linear programming. We will try to think about several open problems, including the famous Hirsh conjecture for polytopes and strongly polynomial algorithms for linear programming.

Time permitting (and depending upon the interests of the class participants) we may cover other topics.

The instructor will give many of the lectures and class participants will give some. Students will be expected to prepare scribe notes for a lecture or two, and work on problems suggested in the lectures. There will be a final project. Listeners and auditors are welcome to attend, and are encouraged to scribe as well.

---

 

Administrative Information

Lectures: TTh 1330-1450     FIRST LECTURE TUES FEB 1           Room 302, CS Bldg.

Professor: Sanjeev Arora - 307 CS Building - 258-3869 arora@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu

Readings, Resources.

Scribe notes have to be written in latex. Scribes should look at files in this subdirectory  starting with  howto.dvi. Scribes should strive for good mathematical style.  A few pages from Mathematical Writing by by Knuth, Larrabee, and Roberts provide some good hints.

• Anupam Gupta and R. Ravi's lecture notes on Metric Space embeddings (from 2003, and a bit out of date by now :)
• Matousek's book chapter on geometric embeddings of finite metric spaces.
• Razborov-Rudich article on Natural proofs
• My own notes about natural proofs and why we should look at nonconstructive methods (excerpted from a forthcoming textbook on Computational Complexity)
• Paper: Expander flows, geometric embeddings and graph partitioning. (Arora, Rao, Vazirani)
• Matousek's writeup of Borsuk-Ulam theorem and its use in the Lovasz-Kneser theorem.
• Survey of linear programming algorithms by Michael Goldwasser (circa 1995)
• Complexity of sign matrices by Linial et al (see here). I'm not sure why this is related to nonconstructive methods, but we'll cover it anyway.
• Measured descent paper of Krauthgamer, Lee, Mendel, Naor  
  
• Euclidean distortion paper of Arora, Lee, Naor.
  
• Is P vs NP formally independent? by Scott Aaronson
• ``The BNS-Chung Criterion for Multi-Party Communication Complexity'', by Ran Raz
• Semidefinite programs and combinatorial optimization by L. Lovasz (highly recommended; everything you need to know in 50-odd pages).
• Lift and project methods (my old lecture notes).
  
  

• ---

  Lecture Schedule

1. Introduction to metric space embeddings, the main questions, a few examples of upperbounds and lowerbounds.
2. Focus on l_1: tree metrics embed isometrically into l_1. Enflo's lowerbound. Connection of l_1 embeddings to approximations for SPARSEST CUT.
3. Embedding every metric space into l_1 with distortion O(log n) [FRT proof] and derivation of Leighton-Rao theorem.
4. Finish FRT.
5. [ARV]
   
6. (canceled lecture)
7. [ARV]
8. Other approx. algorithms using [ARV] (presentation by Yuri Makarychev)
   
9. Apprx. algorithm for Min-2CNF deletion  (presentation by Yuri Makarychev); some warmup remarks for Bourgain's theorem
10. Bourgain;s theorem (KLMN proof)
    
11. Embeddings contd: l_1 into l_2 [ALN]
12. (March 10) Start of nonconstructive methods. Natural proofs and why they won't suffice to separate P from NP.
    
13. Borsuk-Ulam theorem; various formulations. Proof of Lovasz-Kneser theorem from BU. Sketch of proof of existence of Nash's equilibrium from Brouwer fixed point theorem. Distinction between NP-style statements (a Nash Equil. exists) and coNP-style statements (the chromatic number of the Kneser graph is at least X).
    
14. (Mar24) Guest lecturer: Noga Alon. Examples of NP-style nonconstructive statements proved using techniques from topology (BU), algebra, and probability theory.
15. Communication complexity and discrepancy (2-party case).  Methods to upperbound the discrepancy.
    
16. (Mar 31) Multiparty comm. complexity. BNS lowerbound using discrepancy (Raz's proof). Connection to P v/s ACC_0.
17.  
18.  LP and SDP duality as a proof technique. Proof of Roth's 1/4 theorem on discrepancy.
    
19.  Proof of Roth's theorem contd.
    
20.  Lift and project method (Sherali Adams). Explanation of SDP duality.
    
21. (Apr 19) Karmarkar's algorithm for linear programmming
22. Karmarkar contd.
23. (Elad Hazan lectures) Analysis of a randomized simplex algorithm (Kalai, etc.)
24. Kalai etc. contd.
    

         Scribe Notes

1. Lecture 1. Intro to geometric embeddings some major problems.
2. Lecture 2.  Focus on l_1. Enflo's lowerbound for embedding l_1 into l_2. Examples of l_1 and an exact characterization using cut cone.
3. Lectures 3, 4. Embedding every n-point metric into l_1 with distortion O(log n) [FRT proof] and applications to sparsest cut.
   
4. Lectures 4, 5.  ARV approximation for SPARSEST CUT.
   
5. Lecture 8-9. Approximating Min-UnCut and Min-2-CNF-deletion  using ARV/Lee Structure Theorem.
   
6. Lecture 10, the proof of Bourgain's theorem using measured descent.
7. Lecture 11, overview of Arora-Lee-Naor result on embedding l_1 into l_2
8. Lecture 12, Natural proofs
9. Lecture 13, Borsuk Ulam, Lovasz-Kneser Thm.
10. Lecture 14, Guest lecture by Noga Alon on three nonconstructive (NP-type) theorems.
11. Lecture 15, Communication complexity (2-party case) and upperbounding the discrepancy.
12. Chapter on communication complexity from my forthcoming book. (Still a bit incomplete in places.)
13.  
14. Lecture 20: Lift and project relaxations (including for multi-party discrepancy) and SDP duality theory.