A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching

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

10 Scopus citations

Abstract

We prove a lower bound on the space complexity of two-pass semi-streaming algorithms that approximate the maximum matching problem. The lower bound is parameterized by the density of Ruzsa- Szemeredi graphs: • fiany two-pass semi-streaming algorithm for maximum matching has approximation ratio at most 1(log RS(n) log n ) , where RS(n) denotes the maximum number of induced matchings of size (n) in any n-vertex graph, i.e., the largest density of a Ruzsa-Szemeredi graph. Currently, it is known that n(1=log log n) RS(n) n 2O(log(n)) and closing this (large) gap between upper and lower bounds has remained a notoriously diffcult problem in combinatorics. Under the plausible hypothesis that RS(n) = n(1), our lower bound is the first to rule out small-constant approximation two-pass semi-streaming algorithms for the maximum matching problem, making progress on a longstanding open question in the graph streaming literature.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PublisherAssociation for Computing Machinery
Pages708-742
Number of pages35
ISBN (Electronic)9781611977073
StatePublished - 2022
Event33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States
Duration: Jan 9 2022Jan 12 2022

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2022-January

Conference

Conference33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Country/TerritoryUnited States
CityAlexander
Period1/9/221/12/22

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching'. Together they form a unique fingerprint.

Cite this