In this talk, I will describe a framework for approximately solving flow problems in capacitated, undirected graphs, and I will apply it to find approximately maximum s-t flows in almost-linear time, improving on the best previous bound of Õ(mn^{1/3}).

In describing the algorithm, I will discuss several technical tools that may be of independent interest:

• a non-Euclidean generalization of gradient descent, bounds on its performance, and a way to use this to reduce approximate maximum flow and maximum concurrent flow to oblivious routing;
• the definition and efficient construction of a new type of flow sparsifier that ameliorates the longstanding gap between the algorithmic efficacy of sparsification on flow and cut problems; and
• the first almost-linear-time construction of an O(m^{o(1)})-competitive oblivious routing scheme.

This framework is quite flexible, and it readily generalizes to a broader range of graph problems. If time permits, I will briefly discuss how it can be applied, without any substantial modification, to obtain similar speedups for multicommodity flow problems as well.

This is joint work with Lorenzo Orecchia, Aaron Sidford, and Yin Tat Lee.

We study the problem of sketching an input graph, so that, given the sketch, one can estimate the value (capacity) of any cut in the graph up to a small approximation, 1+epsilon. Classical constructions imply sketches of size essentially proportional to n and the square of 1/epsilon [Benczur, Karger 1996].

We construct sketches whose size is only linear in 1/epsilon (and n*polylog n). The improved size comes at a cost of a slightly weaker guarantee: our construction is a randomized scheme which, given accuracy epsilon and an n-vertex graph G=(V,E), produces a sketch from which the capacity of any cut (S,V\S) can be reported, with high probability, within approximation factor (1+epsilon).

We also show the improved dependence on epsilon is possible only under the weaker guarantee: namely, if a sketch succeeds in estimating the capacity of all cuts (S,V\S) in the graph simultaneously, it must be of size Omega(n/epsilon^2) bits.

The Laplacian Solvers World Championships are coming! Outperform the competition and become a world champion!

We are in the process of organizing the first Laplacian World Championships, where solvers for Laplacian linear systems of equations will compete against one another. Our aim is to promote implementation efforts, engineering of high-performance codes, and meaningful comparisons of different algorithms and codes.

The talk will justify the need for this and will describe our proposed structure of the championships. I am hoping for a lively discussion with feedback and suggestions as to how to structure this effort.

Many randomized algorithms employ Markov chains, and the mixing time of the chain is often the main term in the running time. A sequence of Markov chains is said to exhibit cutoff if the total variation distance to stationarity decreases from near 1 to near zero within a short time window (negligible to the mixing time). E.g. lazy walk on the hypercube exhibits cutoff, but lazy walk on the cycle does not. A necessary condition for cutoff is that the product of the spectral gap and the mixing time tends to infinity along the sequence; we prove that this condition is also sufficient for a lazy reversible chain, provided that the hitting times of certain large sets are concentrated. The proof is based on a maximal inequality that also yields sharp bounds for surprise probabilities in reversible chains.

Talk based on joint works with Riddhi Basu and Jonathan Hermon http://arxiv.org/abs/1409.3250 and with James Norris and Alex Zhai http://arxiv.org/abs/1408.0822, both to appear in SODA 2015.

Fast iterative methods developed in Convex Optimization play a crucial role in a number of recent breakthroughs in the design of nearly-linear-time algorithms for fundamental combinatorial problems, such as maximum flow and graph partitioning. Multiplicative Weight Updates, Gradient Descent, and Nesterov’s Method have become a mainstay in the construction and analysis of fast algorithms. The power of these approaches raises a number of questions: What is the exact relation between Multiplicative Weight Updates and Gradient Descent? Why do Multiplicative Weight Updates show up in so many settings? What is the intuition behind Nesterov’s iterative algorithm that achieves the asymptotically optimal iteration count for smooth convex functions?

In this survey talk, I will provide some answers by presenting a unified framework that reveals the power and limitations of each method and provides much needed geometric intuition. Among other insights, I will explain how Multiplicative Weight Updates are a particular instance of a dual iterative method, known as Mirror Descent, and how Nesterov’s algorithm can be naturally derived as a combination of Mirror and Gradient Descent.

As an example of the application of these insights, I will also discuss their crucial role in recent progress in the nearly-linear-time solution of packing linear programs and in the construction of linear-sized sparsifiers.

The material in this talk is joint work with Zeyuan Allen-Zhu (MIT) and Zhenyu Liao (BU).