A new technique for solving ‘graph Laplacians’ is
drastically simpler than its predecessors, with implications for a huge range
of practical problems.
In the last decade, theoretical computer science has seen
remarkable progress on the problem of solving graph Laplacians — the esoteric
name for a calculation with hordes of familiar applications in scheduling,
image processing, online product recommendation, network analysis, and scientific
computing, to name just a few. Only in 2004 did researchers first propose an
algorithm that solved graph Laplacians in “nearly linear time,” meaning that
the algorithm’s running time didn’t increase exponentially with the size of the
problem.