Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma

[2104.04908] Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Computer Science > Data Structures and Algorithms arXiv:2104.04908 (cs) [Submitted on 11 Apr 2021 ( v1 ), last revised 15 Aug 2026 (this version, v2)] Title: Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma Authors: Sepehr Assadi , Vishvajeet N View a PDF of the paper titled Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma, by Sepehr Assadi and Vishvajeet N View PDF 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+\epsilon)$-approximation requires either $n^{\Omega(1)}$ space or $\Omega(1/\epsilon)$ 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/\epsilon)})$ 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 $\delta > 0$ over random guessing, then it cannot solve XOR of $\ell$ independent copies of the problem with advantage better than $\delta^{\Omega(\ell)}$. This result can be of independent interest and useful for other streaming lower bounds as well. Comments: In STOC 2021. 59 pages, 7 Figures. Version 2 fixes an error in the previous proof of the streaming XOR lemma Subjects: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC) Cite as: arXiv:2104.04908 [cs.DS] (or arXiv:2104.04908v2 [cs.DS] for this version) https://doi.org/10.48550/arXiv.2104.04908 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Sepehr Assadi [ view email ] [v1] Sun, 11 Apr 2021 03:36:02 UTC (127 KB) [v2] Sat, 15 Aug 2026 10:36:23 UTC (127 KB) Full-text links: Access Paper: View a PDF of the paper titled Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma, by Sepehr Assadi and Vishvajeet N View PDF TeX Source view license Current browse context: cs.DS < prev | next > new | recent | 2021-04 Change to browse by: cs cs.CC References & Citations NASA ADS Google Scholar Semantic Scholar DBLP - CS Bibliography listing | bibtex Sepehr Assadi export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Automated Inference of Graph Transformation Rules#622689
• DJPlus: Generating minimal test suites for strong coverage criteria in graph models#668101
• CMSO-transductions for tree-like graph decompositions#1156169
• DJPlus: Generating minimal test suites for strong coverage criteria in graph models#986572
• PromptGraph: Graph-Guided Prompt Sanitization for Balancing Privacy and Utility in LLM Inference#363182