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).

# Uploaded 465 Plays 0 Comments


Kavli Frontiers of Science PRO

This channel contains session presentations that cover mathematical topics from the Kavli Frontiers of Science symposium series of the National Academy of Sciences.

For additional symposium information, please visit our web site (

Browse This Channel

Shout Box

Heads up: the shoutbox will be retiring soon. It’s tired of working, and can’t wait to relax. You can still send a message to the channel owner, though!

Channels are a simple, beautiful way to showcase and watch videos. Browse more Channels.