Algorithms & Randomness Center (ARC)
Sanjeev Khanna (University of Pennsylvania)
September 19, 2022
Klaus 1116 - 11:00 am
Title: On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Abstract: We present a new approach for finding matchings in dense graphs by building on Szemeredi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit (very) slight improvements over long standing bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for $n$-vertex graphs:
(a) A single-pass streaming algorithm that finds a near-optimal matching in $o(n^2)$ bits of space. This constitutes the first single-pass, sublinear-space algorithm that improves over the trivial $1/2$-approximation of the greedy algorithm.
(b) A fully dynamic algorithm that with high probability maintains a near-optimal matching in $o(n)$ worst-case update time per edge update, improving upon the previous best update time. The algorithm works even against an adaptive adversary.
The key idea behind both these results is to maintain a matching cover which is a “sparse” subgraph that approximately preserves matchings in each induced subgraph of the input graph. However, given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some function of $(log* n)$. Nevertheless, these results show that the “right” answer to these problems is not what is dictated by the previous bounds.
This is joint work with Sepehr Assadi, Soheil Behnezhad, and Huan Li.
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
