Polynomial pass lower bounds for graph streaming algorithms

DOI10.1145/3313276.3316361MaRDI QIDQ5212768zbMATH OpenOpenAlexFDO

Authors Sepehr Assadi, Yu Chen, Sanjeev Khanna

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.04720

zbMATH Keywords

communication complexitygraph streaminglower bounds

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Abstract: We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instance, we show that any streaming algorithm that finds a weighted minimum $s$-$t$ cut in an $n$-vertex undirected graph requires $n^{2-o(1)}$ space unless it makes $n^{Omega(1)}$ passes over the stream. To prove our lower bounds, we introduce and analyze a new four-player communication problem that we refer to as the hidden-pointer chasing problem. This is a problem in spirit of the standard pointer chasing problem with the key difference that the pointers in this problem are hidden to players and finding each one of them requires solving another communication problem, namely the set intersection problem. Our lower bounds for graph problems are then obtained by reductions from the hidden-pointer chasing problem. Our hidden-pointer chasing problem appears flexible enough to find other applications and is therefore interesting in its own right. To showcase this, we further present an interesting application of this problem beyond streaming algorithms. Using a reduction from hidden-pointer chasing, we prove that any algorithm for submodular function minimization needs to make $n^{2-o(1)}$ value queries to the function unless it has a polynomial degree of adaptivity.

Recommendations

• Superlinear lower bounds for multipass graph processing
• Intractability of min- and max-cut in streaming graphs
• Tight bounds for graph problems in insertion streams
• Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination
• Graph Sparsification in the Semi-streaming Model

Cited in

(12)

• Intractability of min- and max-cut in streaming graphs
• Space lower bounds for graph stream problems
• Superlinear lower bounds for multipass graph processing
• Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination
• The streaming complexity of cycle counting, sorting by reversals, and other problems
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Linearly representable submodular functions: an algebraic algorithm for minimization
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• Rounds vs. communication tradeoffs for maximal independent sets
• Pointer chasing with unlimited interaction
• Cut-query algorithms with few rounds
• Almost optimal superconstant-pass streaming lower bounds for reachability

This page was built for publication: Polynomial pass lower bounds for graph streaming algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212768)