No abstract available.
Monday, November 27th, 2017
1:20 pm–1:30 pm
1:30 pm–2: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 pm–2:30 pm
Speaker: Aaron Sidford, Stanford University
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 pm–4:00 pm
Speaker: Yuanzhi Li, Princeton University
No abstract available.
4:00 pm–4:30 pm
Speaker: Rasmus Kyng, Yale University
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.
