Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

作者: Sepehr Assadi , Huacheng Yu , Gillat Kol , Raghuvansh R. Saxena

DOI:

关键词: Streaming algorithmMathematicsCombinatoricsUpper and lower boundsCycle countMaximum cutCorollaryMatching (graph theory)OmegaLogarithm

摘要: Consider the following gap cycle counting problem in streaming model: The edges of a $2$-regular $n$-vertex graph $G$ are arriving one-by-one stream and we promised that is disjoint union either $k$-cycles or $2k$-cycles for some small $k$; goal to distinguish between these two cases. Verbin Yu [SODA 2011] introduced this showed any single-pass algorithm solving it requires $n^{1-\Omega(\frac{1}{k})}$ space. This result technique behind it---the Boolean Hidden Hypermatching communication problem---has since been used extensively proving lower bounds various problems. Despite its significance broad range applications, bound comes with key weakness inherited by all subsequent results: hard only if there exactly one round can be solved logarithmic rounds. Therefore, derived from hold algorithms. We prove first multi-pass problem: Any $p$-pass vs $2k$-cycles---or even Hamiltonian cycle---requires $n^{1-\frac{1}{k^{\Omega(1/p)}}}$ As corollary result, extend many previous For instance, now $(1+\epsilon)$-approximates value MAX-CUT, maximum matching size, rank an $n$-by-$n$ matrix, $n^{\Omega(1)}$ space $\Omega(\log{(\frac{1}{\epsilon})})$ passes. problems, prior work left open possibility $O(\log{n})$

参考文章(82)
Kook Jin Ahn, Sudipto Guha, Andrew McGregor, Spectral Sparsification in Dynamic Graph Streams Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. pp. 1- 10 ,(2013) , 10.1007/978-3-642-40328-6_1
Andrew McGregor, Finding Graph Matchings in Data Streams Lecture Notes in Computer Science. pp. 170- 181 ,(2005) , 10.1007/11538462_15
Farid Ablayev, Lower Bounds for One-way Probabilistic Communication Complexity international colloquium on automata languages and programming. pp. 241- 252 ,(1993) , 10.1007/3-540-56939-1_76
Michael Kapralov, Better bounds for matchings in the streaming model symposium on discrete algorithms. pp. 1679- 1697 ,(2013) , 10.5555/2627817.2627938
Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, Rasmus Pagh, Triangle Counting in Dynamic Graph Streams Algorithmica. ,vol. 76, pp. 259- 278 ,(2016) , 10.1007/S00453-015-0036-4
Marc Bury, Chris Schwiegelshohn, Sublinear Estimation of Weighted Matchings in Dynamic Data Streams european symposium on algorithms. pp. 263- 274 ,(2015) , 10.1007/978-3-662-48350-3_23
Kook Jin Ahn, Sudipto Guha, Graph Sparsification in the Semi-streaming Model Automata, Languages and Programming. pp. 328- 338 ,(2009) , 10.1007/978-3-642-02930-1_27
Michael Kapralov, Ashish Goel, Sanjeev Khanna, On the communication and streaming complexity of maximum bipartite matching symposium on discrete algorithms. pp. 468- 485 ,(2012) , 10.5555/2095116.2095157
Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik, How Hard Is Counting Triangles in the Streaming Model? Automata, Languages, and Programming. pp. 244- 254 ,(2013) , 10.1007/978-3-642-39206-1_21
Madhu Sudan, Michael Kapralov, Sanjeev Khanna, Streaming lower bounds for approximating MAX-CUT symposium on discrete algorithms. pp. 1263- 1282 ,(2015) , 10.5555/2722129.2722213