Open Lecture — The Revolution in Graph Theoretic Optimization

Graph theoretic optimization problems that have been dormant for fifty years are now seeing new and exciting algorithms. These advances have been made possible by Spectral Graph Theory, the interplay between linear algebra and combinatorial graph theory. One application of this interplay is a nearly linear time solver for Symmetric Diagonally Dominant systems (SDD). This seemingly restrictive class of linear systems has received substantial interest in the last fifteen years, and there is an ever growing list of problems that are amenable to SDD solvers, including image segmentation, image denoising, finding solutions to elliptic equations, computing maximum flow in a graph, and graph sparsification. All these examples can be viewed as special cases of convex optimization problems on graphs.

Possibly the best known graph theoretic optimization problem is computing the maximum flow in a graph. Again, using spectral graph theory, the maximum flow problem in undirected graphs can now be approximately solved in almost linear time. I claim that this is only the beginning of a new era in efficient algorithm design.

In this talk I will describe a world not too far in the future in which such optimization problems, which a priori seem to require at least quadratic work, will all be solvable by genuinely practical algorithms that are guaranteed to run in near linear time and are highly parallel.

Light refreshments will be served before the lecture at 3:30 p.m.