Monday, November 27th, 2017

1:30 pm2:00 pm

As we all know, Michael has read the proof from the book and gave out some proofs to us from time to time. In this talk, I will describe two of his proofs, one proof is about an input sparsity algorithm for Ax=b by uniform sampling. Another proof is about how to solve a sequence of slowly changing linear systems faster.

2:00 pm2:30 pm

Oblivious routing is a fundamental problem in combinatorial optimization and a key primitive that has been used to speed up the running times for various problems ranging from maximum flow, to multicommodity flow, to minimum cost flow. In this talk I will survey some of Michael's beautiful work in this area. In general, Michael's results had a tendency to simplify previous approaches and strike at the heart what made problems solvable. His work on oblivious routing was no exception; it was the first project I ever discussed with him and it changed how I thought about problems in this area.

3:30 pm4:00 pm
Speaker: Yuanzhi Li, Princeton University

No abstract available.

4:00 pm4:30 pm

A sequence of recent works has led to the development of nearly-linear time solvers for linear equations in Directed Laplacians. Among other things, this gives the first nearly-linear time algorithm for computing the stable distribution of directed random walks. I'll talk about the overall approach to solving these equations, developed by Michael and his co-authors, and I'll outline how we combined it with approximate Gaussian elimination to get the first nearly-linear time solver for Directed Laplacians.

4:30 pm5:00 pm

No abstract available.