On Regularity Lemma and Barriers in Streaming and Dynamic Matching

Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

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: 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é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.

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages131-144
Number of pages14
ISBN (Electronic)9781450399135
DOIs
StatePublished - Jun 2 2023
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period6/20/236/23/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Dynamic Algorithms
  • Maximum Matching
  • Regularity Lemma
  • Streaming Algorithms

Fingerprint

Dive into the research topics of 'On Regularity Lemma and Barriers in Streaming and Dynamic Matching'. Together they form a unique fingerprint.

Cite this