"We know that God exists because mathematics is consistent and we know that the devil exists because we cannot prove the consist

Menachem Kojman
Ben Gurion University of the Negev; Member, School of Mathemtics
April 6, 2011

MATHEMATICAL CONVERSATIONS

"We know that God exists because mathematics is consistent and we know that the devil exists because we cannot prove the consistency." -- Andre Weil

Graph Sparsification by Edge-Connectivity and Random Spanning Trees

Nick Harvey
University of Waterloo
April 11, 2011

A "sparsifier" of a graph is a weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of (1 +/- eps). Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging applications, including fast network flow algorithms, fast linear system solvers, etc. Batson, Spielman and Srivastava (2009) showed that sparsifiers with O(n/eps^2) edges exist, and they can be computed in time poly(n,eps).