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:

• 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.

• Read Chapter 1 of Doyle and Snell's book “Random Walks and Electrical Networks” .
• The first lecture will be on Thursday, August 25.
• We will be using Piazza as an online discussion forum.

Instructor:

Bobby Kleinberg rdk@cs. 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.

• The mailing list is cs6822-l@cs.cornell.edu. If you have not received a message welcoming you to the mailing list, please subscribe by visiting https://lists.cs.cornell.edu/mailman/listinfo/cs6822-l.
• 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.