18.408 An Algorithmist's Toolkit

Course Information:

This course will cover a collection of geometric and analytic techniques that apply broadly in modern algorithm design.  The exact topics covered will depend on student interest, but a (perhaps overly ambitious) set of possibilities includes:

Spectral Graph Theory:
Graph Laplacians and their eigenvalues, connections to random walks and mixing, isoperimetric and Cheeger inequalities, expanders, and random graphs, as well as recent advances in algorithmic directed spectral graph theory. Applications to include the analysis of Markov chains, graph cutting, clustering, approximate counting, disjoint path problems, routing, and graph drawing.

Convex Geometry:
Geometric properties of high-dimensional convex bodies, Fritz John's theorem and isotropy, Brunn-Minkowski and isoperimetric inequalities, Dvoretzky's theorem, concentration of measure, and connections to probability theory.  Applications to include volume computation , dimension reduction, and convex programming.

Iterative Methods for Optimization and Linear Algebra:
How to use geometric information to quickly solve convex programs, linear systems, and eigenvalue problems.  Will study and compare a variety of iterative methods including gradient descent and its generalizations, multiplicative weights, the Lanczos algorithm,  conjugate gradients, Nesterov's accelerated gradient method, stochastic gradient descent, and coordinate descent. Will also study how to use problem structure to accelerate iterative methods through preconditioning and its recent generalizations.  Applications to include fast graph algorithms, machine learning, numerical linear algebra, online algorithms, ``boosting'' in learning and complexity theory, and zero-sum games.

Graphs, Linear Systems, and Electrical Networks:
The relationship between networks of electrical resistors and Laplacian linear systems, and how to use this to probe both the combinatorial structure of the graph and the algebraic structure of the Laplacian.  Applications to include the analysis of random processes and fast algorithms for graph sparsification.

Graph Decomposition, Approximation, and Embedding:
Techniques for relating the properties of a graph to those of other (ideally smaller or simpler) graphs or distributions of graphs.  Applications to include fast algorithms for maximum flow/minimum cut, approximating NP-hard graph problems, and oblivious routing.  

Lattices and Basis Reduction:
Basic properties of lattices, Minkowski's theorem, and the LLL algorithm.  Applications to include solving low-dimensional integer programs and breaking cryptosystems.