Graph and Hypergraph Sparsification
23 gennaio 2020 alle 11:00
Sala Consiglio 8 Piano, via Celoria 18
Speaker: Luca Trevisan, Università Bocconi
Persona di riferimento: Nicolò Cesa-Bianch
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 hypergraph.
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.)
Luca Trevisan is a professor of Computer Science at Bocconi University. Luca studied at the Sapienza University of Rome, he was a post-doc at MIT and at DIMACS, and he was on the faculty of Columbia University, U.C. Berkeley, and Stanford, before returning to Berkeley in 2014 and, at long last, moving back to Italy in 2019. Luca's research is focused on computational complexity, on analysis of algorithms, and on problems at the intersection of pure mathematics and theoretical computer science. Luca received the STOC'97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians. He is a recipient of a 2019 ERC Advanced Grant.i