Approaching optimality for solving SDD linear systems

We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k, produces an incremental sparsifier ˆ G with n−1+m=k edges, such that the condition number of G with ˆ G is bounded above by ˜ O(k log 2 n) 1 , with probability 1 − p. The algorithm runs in time