March 10, 2023
Our speaker for this week’s theory seminar is Huan Li, a PhD student here at Penn. The talk will take place in Levine 307 on Friday 3/10 at 1pm.
Title: On Weighted Graph Sparsification by Linear Sketching
Abstract: A seminal work of [Ahn-Guha-McGregor, PODS'12] showed that one can compute a cut sparsifier of an unweighted undirected graph by taking a near-linear number of linear measurements on the graph. Subsequent works also studied computing other graph sparsifiers using linear sketching, and obtained near-linear upper bounds for spectral sparsifiers [Kapralov-Lee-Musco-Musco-Sidford, FOCS'14] and first non-trivial upper bounds for spanners [Filtser-Kapralov-Nouri, SODA'21].