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]. All these linear sketching algorithms, however, only work on unweighted graphs.
In this talk, we present several new results for weighted graph sparsification by linear sketching, consisting of both algorithms and lower bounds. Our results suggest some interesting separation between weighted cut and spectral sparsification, which is in sharp contrast to the unweighted case where both types of sparsification require roughly the same number of measurements.
Based on joint work with Yu Chen and Sanjeev Khanna in FOCS 2022.