Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma

Sepehr Assadi, N. Vishvajeet

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

Abstract

We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a (1+?)-approximation requires either n?(1) space or ?(1/?) passes, even on highly restricted families of graphs such as bounded-degree planar graphs. For multiple of these problems, this bound matches those of existing algorithms and is thus (asymptotically) optimal. Our results considerably strengthen prior lower bounds even for arbitrary graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there has been a plethora of lower bounds for single-pass algorithms for these problems; however, the only multi-pass lower bounds proven very recently in [Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with exponentially smaller o(log(1/?)) passes for these problems. One key ingredient of our proofs is a simple streaming XOR Lemma, a generic hardness amplification result, that we prove: informally speaking, if a p-pass s-space streaming algorithm can only solve a decision problem with advantage ?> 0 over random guessing, then it cannot solve XOR of ? independent copies of the problem with advantage much better than ?. This result can be of independent interest and useful for other streaming lower bounds as well.

Original languageEnglish (US)
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery
Pages612-625
Number of pages14
ISBN (Electronic)9781450380539
DOIs
StatePublished - Jun 15 2021
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: Jun 21 2021Jun 25 2021

Publication series

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

Conference

Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Country/TerritoryItaly
CityVirtual, Online
Period6/21/216/25/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Communication Complexity
  • Graph Streaming
  • MAXCUT
  • Pointer Chasing
  • Property Testing
  • XOR lemma

Fingerprint

Dive into the research topics of 'Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma'. Together they form a unique fingerprint.

Cite this