Computer Science 598B
Seminar in Algorithms and Complexity
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 NP-hard optimization problems.
- 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
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
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
we may cover other topics.
The instructor will give many of the lectures and class
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.
Lectures: TTh 1330-1450 FIRST LECTURE TUES
Room 302, CS Bldg.
Arora - 307
CS Building - 258-3869 firstname.lastname@example.org
Graduate Coordinator: Melissa Lawson
- 310 CS Building - 258-5387 email@example.com
Scribe notes have to be written in
latex. Scribes should look at files in this
starting with howto.dvi. Scribes should strive for
good mathematical style.
few pages from Mathematical Writing by by Knuth,
Larrabee, and Roberts provide some good hints.
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
- 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,
- Matousek's writeup
of Borsuk-Ulam theorem and its use in the Lovasz-Kneser theorem.
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.
descent paper of Krauthgamer, Lee, Mendel, Naor
distortion paper of Arora, Lee, Naor.
- Is P vs NP
formally independent? by Scott Aaronson
BNS-Chung Criterion for Multi-Party Communication Complexity'',
by Ran Raz
programs and combinatorial optimization by L. Lovasz (highly
recommended; everything you need to know in 50-odd pages).
- Lift and project methods (my old
- 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
- Embedding every metric space into l_1 with distortion O(log n)
[FRT proof] and derivation of Leighton-Rao theorem.
- Finish FRT.
- (canceled lecture)
- Other approx. algorithms using [ARV] (presentation by Yuri
- Apprx. algorithm for Min-2CNF deletion (presentation by
Yuri Makarychev); some warmup remarks for Bourgain's theorem
- Bourgain;s theorem
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.
- 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).
- (Mar24) Guest lecturer: Noga Alon. Examples of NP-style
nonconstructive statements proved using techniques from topology (BU),
algebra, and probability theory.
- Communication complexity and discrepancy (2-party 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
- (Apr 19) Karmarkar's algorithm for linear programmming
- Karmarkar contd.
- (Elad Hazan lectures) Analysis of a randomized simplex algorithm
- Kalai etc. contd.
- 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 n-point
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 8-9. Approximating Min-UnCut
and Min-2-CNF-deletion using ARV/Lee Structure Theorem.
- Lecture 10, the proof of Bourgain's
theorem using measured descent.
- Lecture 11, overview of
Arora-Lee-Naor result on embedding l_1 into l_2
- Lecture 12, Natural proofs
- Lecture 13, Borsuk Ulam, Lovasz-Kneser
- Lecture 14, Guest lecture by Noga
Alon on three nonconstructive (NP-type) theorems.
- Lecture 15, Communication complexity
(2-party 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 multi-party discrepancy) and SDP duality theory.