Every Graph has a Sparse Approximation
Nikhil Srivastava, Microsoft Research, India
Graphs are ubiquitous in modern science. The internet, social networks, electrical circuits, road maps, and the brain can all be viewed as graphs. One natural measure of the complexity of a graph is the number of edges it has; this number can vary widely, and we refer to a graph with few edges as sparse, and a graph with many (say, much greater than the number of nodes) edges as dense.
I will survey a recent line of work with Batson, Spielman, and Teng which shows that *every* graph can be approximated by one which is very sparse. This is desirable because sparse graphs are easier and cheaper to store and compute with, and often easier to understand than dense ones.
The above plays an important role in the breakthrough algorithm of Spielman and Teng for solving certain linear equations arising from graphs very quickly. In particular, their algorithm allows one to simulate certain physical processes on graphs, such as electrical flow, heat flow, and random walk, on a computer as fast as theoretically possible (essentially, in the amount of time it takes to read the input).