"We know that God exists because mathematics is consistent and we know that the devil exists because we cannot prove the consistency." -- Andre Weil
GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR
Note: (joint work with O. Brinon and A. Mokrane)
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).