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

We continue the study of the communication complexity of gap cycle countingproblems. These problems have been introduced by Verbin and Yu [SODA 2011] andhave found numerous applications in proving streaming lower bounds. In thenoisy gap cycle counting problem (NGC), there is a small integer $k \geq 1$ andan $n$-vertex graph consisted of vertex-disjoint union of either $k$-cycles or$2k$-cycles, plus $O(n/k)$ disjoint paths of length $k-1$ in both cases(``noise''). The edges of this graph are partitioned between Alice and Bobwhose goal is to decide which case the graph belongs to with minimalcommunication from Alice to Bob.  We study the robust communication complexity -- `a la Chakrabarti, Cormode,and McGregor [STOC 2008] -- of NGC, namely, when edges are partitioned randomlybetween the players. This is in contrast to all prior work on gap cyclecounting problems in adversarial partitions. While NGC can be solved triviallywith zero communication when $k < \log{n}$, we prove that when $k$ is aconstant factor larger than $\log{n}$, the robust (one-way) communicationcomplexity of NGC is $\Omega(n)$ bits.  As a corollary of this result, we can prove several new graph streaming lowerbounds for random order streams. In particular, we show that any streamingalgorithm that for every $\varepsilon > 0$ estimates the number of connectedcomponents of a graph presented in a random order stream to within an$\varepsilon \cdot n$ additive factor requires $2^{\Omega(1/\varepsilon)}$space, settling a conjecture of Peng and Sohler [SODA 2018]. We further discussnew implications of our lower bounds to other problems such as estimating sizeof maximum matchings and independent sets on planar graphs, random walks, aswell as to stochastic streams.

(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond