Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with streaming:
TR13-002 | 31st December 2012
Venkatesan Guruswami, Krzysztof Onak

Superlinear lower bounds for multipass graph processing

Revisions: 3

We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:

* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),

* testing if two ... more >>>

TR15-083 | 14th May 2015
Omri Weinstein, David Woodruff

The Simultaneous Communication of Disjointness with Applications to Data Streams

We study $k$-party set disjointness in the simultaneous message-passing model, and show that even if each element $i\in[n]$ is guaranteed to either belong to all $k$ parties or to at most $O(1)$ parties in expectation (and to at most $O(\log n)$ parties with high probability), then $\Omega(n \min(\log 1/\delta, \log ... more >>>

TR15-111 | 8th July 2015
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

Low Distortion Embedding from Edit to Hamming Distance using Coupling

Revisions: 1

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. ... more >>>

TR18-129 | 13th July 2018
Jelani Nelson, Huacheng Yu

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Revisions: 1

We show optimal lower bounds for spanning forest computation in two different models:

* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the ... more >>>

ISSN 1433-8092 | Imprint