Computer Science 6822
Advanced Topics in Theory of Computing:
Flows, Cuts, and Sparsifiers

Cornell University, Fall 2011

Course Description

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:

Announcements Staff and Office Hours

Bobby Kleinberg
4138 Upson
Office hours: Wed. 4-5pm, or by appointment
Phone: 255-9200


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