
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.
 Geometric embeddings of finite metric spaces, which
has led to several breakthroughs in recent years, including new
approximation algorithms for several NPhard optimization problems.
 Nonconstructive methods in theoretical CS and
combinatorics. This is not a wellestablished 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.
 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 13301450 FIRST LECTURE TUES
FEB 1
Room 302, CS Bldg.
Professor: Sanjeev
Arora  307
CS Building  2583869 arora@cs.princeton.edu
Graduate Coordinator: Melissa Lawson
 310 CS Building  2585387 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.
 RazborovRudich 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 BorsukUlam theorem and its use in the LovaszKneser 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
BNSChung Criterion for MultiParty Communication Complexity'',
by Ran Raz
 Semidefinite
programs and combinatorial optimization by L. Lovasz (highly
recommended; everything you need to know in 50odd pages).
 Lift and project methods (my old
lecture notes).

Lecture Schedule
 Introduction to metric space embeddings, the main questions, a
few examples of upperbounds and lowerbounds.
 Focus on l_1: tree metrics embed isometrically into l_1. Enflo's
lowerbound. Connection of l_1 embeddings to approximations for SPARSEST
CUT.
 Embedding every metric space into l_1 with distortion O(log n)
[FRT proof] and derivation of LeightonRao theorem.
 Finish FRT.
 [ARV]
 (canceled lecture)
 [ARV]
 Other approx. algorithms using [ARV] (presentation by Yuri
Makarychev)
 Apprx. algorithm for Min2CNF deletion (presentation by
Yuri Makarychev); some warmup remarks for Bourgain's theorem
 Bourgain;s theorem
(KLMN proof)
 Embeddings
contd: l_1 into l_2 [ALN]
 (March 10) Start of nonconstructive methods. Natural proofs and
why they won't suffice to separate P from NP.
 BorsukUlam theorem; various formulations. Proof of LovaszKneser
theorem from BU. Sketch of proof of existence of Nash's equilibrium
from Brouwer fixed point theorem. Distinction between NPstyle
statements (a Nash Equil. exists) and coNPstyle statements (the
chromatic number of the Kneser graph is at least X).
 (Mar24) Guest lecturer: Noga Alon. Examples of NPstyle
nonconstructive statements proved using techniques from topology (BU),
algebra, and probability theory.
 Communication complexity and discrepancy (2party case).
Methods to upperbound the discrepancy.
 (Mar 31) Multiparty comm. complexity. BNS
lowerbound using discrepancy (Raz's proof). Connection
to P v/s ACC_0.

 LP and SDP duality as a proof technique. Proof of Roth's
1/4 theorem on discrepancy.
 Proof of Roth's theorem contd.
 Lift and project method (Sherali Adams). Explanation of SDP
duality.
 (Apr 19) Karmarkar's algorithm for linear programmming
 Karmarkar contd.
 (Elad Hazan lectures) Analysis of a randomized simplex algorithm
(Kalai, etc.)
 Kalai etc. contd.
Scribe Notes
 Lecture 1. Intro to geometric
embeddings some major problems.
 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.
 Lectures 3, 4. Embedding every npoint
metric into l_1 with distortion O(log n) [FRT proof] and applications
to sparsest cut.
 Lectures 4, 5. ARV approximation for SPARSEST CUT.
 Lecture 89. Approximating MinUnCut
and Min2CNFdeletion using ARV/Lee Structure Theorem.
 Lecture 10, the proof of Bourgain's
theorem using measured descent.
 Lecture 11, overview of
AroraLeeNaor result on embedding l_1 into l_2
 Lecture 12, Natural proofs
 Lecture 13, Borsuk Ulam, LovaszKneser
Thm.
 Lecture 14, Guest lecture by Noga
Alon on three nonconstructive (NPtype) theorems.
 Lecture 15, Communication complexity
(2party case) and upperbounding the discrepancy.
 Chapter on communication complexity
from my forthcoming book. (Still a bit incomplete in places.)

 Lecture 20: Lift and project relaxations
(including for multiparty discrepancy) and SDP duality theory.