Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BIAS AMPLIFICATION:
Reports tagged with bias amplification:
TR21-083 | 21st June 2021
Mark Braverman, Sumegha Garg, Or Zamir

#### Tight Space Complexity of the Coin Problem

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 >>>

ISSN 1433-8092 | Imprint