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

Author: Sepehr Assadi
Conference: The 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'22).
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:

  • Any two-pass semi-streaming algorithm for maximum matching has approximation ratio at least (1−Ω(logRS(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/loglogn)≤RS(n)≤n/2^O(log∗(n)) and closing this (large) gap between upper and lower bounds has remained a notoriously difficult 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.