All reports by Author Or Zamir:

__
TR21-083
| 21st June 2021
__

Mark Braverman, Sumegha Garg, Or Zamir#### Tight Space Complexity of the Coin Problem

Mark Braverman, Sumegha Garg, Or Zamir

In the coin problem we are asked to distinguish, with probability at least $2/3$, between $n$ $i.i.d.$ coins which are heads with probability $\frac{1}{2}+\beta$ from ones which are heads with probability $\frac{1}{2}-\beta$. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once ... more >>>