On Weighted Graph Sparsification by Linear Sketching

Start Date: March 29, 2023
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Huan Li - University of Pennsylvania
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
Presentation Type: Stand Alone Presentation
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.

Events