Computer Science 6822
Advanced Topics in Theory of Computing:
Flows, Cuts, and Sparsifiers
Cornell University, Fall 2011
Several of the most striking recent developments in algorithms have rested on the beautiful and often surprising interplay between graph theory, geometry, spectral methods, random walks, and the analysis of electrical networks. We will learn about these techniques via their applications to the paradigmatic graph-theoretic problems of single- and multi-commodity flow, graph partitioning, and graph sparsification. Some highlights of the course will include:
Staff and Office Hours
the planar separator theorem and spectral partitioning;
expander graphs: explicit constructions and applications;
the algorithm of Christiano et al. for computing maximum flows using electrical flows;
Batson, Spielman, and Srivastava’s construction of spectral sparsifiers;
multicommodity flows, their applications, and connections to metric embeddings;
oblivious routing schemes and vertex sparsifiers.
Office hours: Wed. 4-5pm, or by appointment
There is no textbook for CS 6822.
We will be learning these topics
through reading the relevant research papers.
The prerequisite is CS 6820 or its equivalent.
(One semester of algorithms at the graduate level.)
Students will produce a set of scribe notes, complete one or two
problem sets, and present one paper or a portion thereof.
There are no exams in CS 6822.
Mailing Lists and Discussion Forum
Basic Course Data
- The mailing list is firstname.lastname@example.org. If you
have not received a message welcoming you to the mailing list,
please subscribe by visiting
- We will be using Piazza
as an online discussion forum for the class. This allows for an open
discussion of questions related to CS 6822, visible to the
instructor and the other students in the course.
- If you have a question for Professor Kleinberg that is
not appropriate for a public discussion, you can always mail him
at the address listed above.
- Time: Tuesday and Thursday, 8:40-9:55.
- Place: Hollister 306.