Daniel A. Spielman

We introduce a notion of what it means for one graph to be a good spectral approximation of another, and prove that every graph can be well-approximated by a graph with few edges.We ask how well a given graph can be approximated by a sparse graph...

Networks describe how things are connected, and are ubiquitous in science and society. Networks can be very concrete, like road networks connecting cities or networks of wires connecting computers. They can represent more abstract connections such as...