Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SPACE LOWER BOUNDS:
Reports tagged with Space Lower Bounds:
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 >>>

ISSN 1433-8092 | Imprint