English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

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