Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings

Sepehr Assadi, Janani Sundaresan

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

1 Scopus citations

Abstract

We prove that any semi-streaming algorithm for (1+ϵ) approximation of maximum bipartite matching requires (Formula Presented) passes, where β ∈(0,1) is the largest parameter so that an n-vertex graph with nβ edge-disjoint induced matchings of size Θ(n) exist (such graphs are referred to as Ruzsa-Szemerédi graphs). Currently, it is known that (Formula Presented) and closing this huge gap between upper and lower bounds has remained a notoriously difficult problem in combinatorics.Under the plausible hypothesis that β=Ω(1), our lower bound result provides the first pass-approximation lower bound for (small) constant approximation of matchings in the semi-streaming model, a longstanding open question in the graph streaming literature.Our techniques are based on analyzing communication protocols for compressing (hidden) permutations. Prior work in this context relied on reducing such problems to Boolean domain and analyzing them via tools like XOR Lemmas and Fourier analysis on Boolean hypercube. In contrast, our main technical contribution is a hardness amplification result for permutations through concatenation in place of prior XOR Lemmas. This result is proven by analyzing permutations directly via simple tools from group representation theory combined with detailed information-theoretic arguments, and can be of independent interest.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PublisherIEEE Computer Society
Pages909-932
Number of pages24
ISBN (Electronic)9798350318944
DOIs
StatePublished - 2023
Event64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, United States
Duration: Nov 6 2023Nov 9 2023

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Country/TerritoryUnited States
CitySanta Cruz
Period11/6/2311/9/23

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • communication complexity
  • graph streaming
  • matching
  • multi pass streaming lower bounds

Fingerprint

Dive into the research topics of 'Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings'. Together they form a unique fingerprint.

Cite this