Computer Science/Discrete Mathematics Seminar I

A weighted graph H is a sparsifier of a graph G if H has much fewer edges than G and, in an appropriate technical sense, H "approximates" G. Sparsifiers are useful as compressed representations of graphs and to speed up certain graph algorithms. In a "cut sparsifier," the notion of approximation is that every cut is crossed by approximately the same number of edges in G as in H. In a "spectral sparsifier" a stronger, linear-algebraic, notion of approximation holds. Similar definitions can be given for hypergraphs. We discuss some new definitions, new constructions and new lower bounds for graph and hypergraph sparsifiers, including: - A new lower bound on the number edges of any spectral sparsifier, which can be seen as a generalization of the Alon-Boppana theorem to graphs that are irregular and weighted; - A new lower bound on the number of bits needed for any data structure that approximately stores the cut information of the graph, showing that known sparsifiers optimally solve this data structure problem - A new definition and constructions of sparsification for graph and hypergraphs, which allows *unweighted* sparsifiers with O(n) edges for all graphs and hypergraphs - A new construction of spectral hypergraph sparsifiers with a nearly-linear number of hyperedges (compared to a cubic number of hyperedges in previous constructions).

Based on joint work with Nikhil Bansal, Charles Carlson, Alexandra Kolla, Nikhil Srivastava and Ola Svensson.