Preconditioning in Expectation

Solving a linear system in the Laplacian of a graph can be reduced to solving a few systems in a sparser approximation of the graph.

Applying this idea recursively has led to the development of a family of nearly-linear time algorithms for solving graph Laplacians. A major obstacle in improving beyond the O~(m log n) running time bound achieved by [Koutis-Miller-Peng '11] was a very strong approximation requirement placed on the sparsifiers used. This issue can be traced back to the 'coupon collector problem'.

We show that using ideas from a different kind of solver introduced in [Kelner-Orecchia-Sidford-Zhu '13] we can relax these requirements, achieving the currently fastest running time of O~(m sqrt(log n)) for Laplacian solvers. The talk is based on the work by Cohen, Kyng, Pachocki, Peng and Rao available at http://arxiv.org/abs/1401.6236.