作者: Sepehr Assadi , Huacheng Yu , Gillat Kol , Raghuvansh R. Saxena
DOI:
关键词: Streaming algorithm 、 Mathematics 、 Combinatorics 、 Upper and lower bounds 、 Cycle count 、 Maximum cut 、 Corollary 、 Matching (graph theory) 、 Omega 、 Logarithm
摘要: 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})$