Huan Li, University of Pennsylvania

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.

See: https://theory.cs.rutgers.edu/theory_seminar