TY - GEN

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

AU - Assadi, Sepehr

N1 - Publisher Copyright:
Copyright © 2022 by SIAM Unauthorized reproduction of this article is prohibited.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85130638986&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130638986&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85130638986

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 708

EP - 742

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -