On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li · 2023
We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs: