@inproceedings{e50750e70d2248fe9d5783d038922766,

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 Szemer{\'e}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: A deterministic single-pass streaming algorithm that finds a (1-o(1))-approximate matching in o(n2) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm. A randomized fully dynamic algorithm that with high probability maintains a (1-o(1))-approximate matching in o(n) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o(n) update-time dynamic algorithm with approximation guarantee arbitrarily close to one. Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log∗ n)(1) factor. Nevertheless, in each case, they show that the {"}right{"}answer to the problem is not what is dictated by the previous bounds. Finally, in the streaming model, we also present a randomized (1-o(1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemer{\'e}di (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.",

keywords = "Dynamic Algorithms, Maximum Matching, Regularity Lemma, Streaming Algorithms",

author = "Sepehr Assadi and Soheil Behnezhad and Sanjeev Khanna and Huan Li",

note = "Publisher Copyright: {\textcopyright} 2023 ACM.; 55th Annual ACM Symposium on Theory of Computing, STOC 2023 ; Conference date: 20-06-2023 Through 23-06-2023",

year = "2023",

month = jun,

day = "2",

doi = "10.1145/3564246.3585110",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "131--144",

editor = "Barna Saha and Servedio, {Rocco A.}",

booktitle = "STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing",

}