Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with heavy hitters:
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 >>>

TR20-162 | 7th November 2020
Dean Doron, Mary Wootters

High-Probability List-Recovery, and Applications to Heavy Hitters

Revisions: 2

An error correcting code $\mathcal{C} \colon \Sigma^k \to \Sigma^n$ is list-recoverable from input list size $\ell$ if for any sets $\mathcal{L}_1, \ldots, \mathcal{L}_n \subseteq \Sigma$ of size at most $\ell$, one can efficiently recover the list $\mathcal{L} = \{ x \in \Sigma^k : \forall j \in [n], \mathcal{C}(x)_j \in \mathcal{L}_j ... more >>>

ISSN 1433-8092 | Imprint