  We show that preconditioners constructed by random sampling can perform well
without meeting the standard requirements of iterative methods. When applied to
graph Laplacians, this leads to ultra-sparsifiers that in expectation behave as
the nearly-optimal ones given by [Kolla-Makarychev-Saberi-Teng STOC`10].
Combining this with the recursive preconditioning framework by [Spielman-Teng
STOC`04] and improved embedding algorithms, this leads to algorithms that solve
symmetric diagonally dominant linear systems and electrical flow problems in
expected time close to $m\log^{1/2}n$ .
