Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with streaming algorithm:
TR07-079 | 11th August 2007
Emanuele Viola, Avi Wigderson

One-way multi-party communication lower bound for pointer jumping with applications

In this paper we study the one-way multi-party communication model,
in which every party speaks exactly once in its turn. For every
fixed $k$, we prove a tight lower bound of
$\Omega{n^{1/(k-1)}}$ on the probabilistic communication
complexity of pointer jumping in a $k$-layered tree, where the
pointers of the $i$-th ... more >>>

TR15-135 | 19th August 2015
Arnab Bhattacharyya, Palash Dey

Fishing out Winners from Vote Streams

Revisions: 1

We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined ... more >>>

TR20-139 | 11th September 2020
Mark Braverman, Sumegha Garg, David Woodruff

The Coin Problem with Applications to Data Streams

Consider the problem of computing the majority of a stream of $n$ i.i.d. uniformly random bits. This problem, known as the {\it coin problem}, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant ... more >>>

TR21-027 | 24th February 2021
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\log n})$-pass streaming algorithm solving the (directed) $s$-$t$ reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including ... more >>>

TR23-189 | 28th November 2023
John Kallaugher, Ojas Parekh, Nadezhda Voronova

Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model

While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been ... more >>>

ISSN 1433-8092 | Imprint