# Tight Space Complexity of the Coin Problem

Today I listened to the excellent talk *Tight Space Complexity of the Coin Problem*, and some brief notes are recorded here.

## Introduction to the Coin Problem

In the talk we will focus on **streaming space complexity** required to distinguish a bias of \(\delta\) w.p. 2/3 on \(n\) coin tosses. For example, \(O(\log k)\) space can distinguish \(\delta = \Omega(1/k)\) by maintaining a counter with threshold \(k\). This algorithm is optimal within \(O(\log k)\) space if *time-invariant*, i.e., don't have access to a clock.

The Coin Problem is statistically solvable when \(\delta = \Omega(n^{-0.5})\) by counting, which is optimal for \(\delta = O(n^{-0.5})\) (equivalently, \(\operatorname{poly}(n)\) width is necessary [BGW20]).

## Coin Problem in ROBPs

Definition of ROBP (*Read Once Branching Program*): width \(w = 2^{\text{space}}\), length (also called depth) \(L = n\).

The work [BGZ21] completes the picture: \(w = n^{\Omega(1)}\) when \(n^{-0.5} < \delta < n^{-1/3}\), and \(w = O(\log n)\) for \(n^{-1/3} < \delta < n^{-0.3}\) (threshold). The talk will discuss the following two parts:

- \(O(\log \log n)\)-memory streaming algorithm for \(\delta \gg n^{-1/3}\) (
**recursive majority**) - \(\Omega(\log n)\)-memory lower bound for \(\delta \ll n^{-1/3}\) (see below)

## Upper Bound for \(\delta \gg n^{-1/3}\)

First we explain the idea for \(\delta = 1/\log n\): ** Tribes with width \(\log n\)** detects bias of \(\Omega(1/\log n)\), implying a width-3 length-\(n\) ROBP. By

**identifying the bias-amplifying gadget and recursing**, we get an \(O((\log n)^w)\) amplification, thus generalize the bound to \(1/\operatorname{polylog}(n)\)-bias case [BV10]. Generally, recursing on size-\(s\) amplification-\(\alpha\) ROBF gives \(\alpha^{\log_s n} = n^{\log_s \alpha}\) amplification, and in [Bop85, DZ97] it's shown that

**best gadget gives \(n^{0.306}\)**.

Here we state a simple fact: simulation of depth-\(d\) ROBF can be done by width-\((d+1)\) ROBP. Moreover, **the ROBP constructed in this way can have only linearly incrementing width on recursing** (while the length is increasing *exponentially*): just translate the recursed ROBF counterpart. Scrutinizing the translation process carefully, we can generalize the fact by introducting the concept of ** effective width**, which is the maximum # nodes in one layer whose transitions depends on the input. By a similar argument we can prove that

**recursing on any ROBP with effective width 1 can be done with only linear increment on width**.

Recurse on width-\(m\) ROBP giving \(m^{1/3}\) amplification with effective width 1 (see below for **the construction of \(r^{1.5}\)-length \(r^{1.5}\)-width ROBP with effective width 1, giving amplification of \(r^{0.5}\)**) \(\log_{m^{1.5}} n\) times, we will get \(n^{1/3}\) amplification, within width \(O(\log n)\) (ROBF depth \(O(\log n) \times m^{1.5}\)).

## Sequences Capturing Random Walks

Given a sequence \(b_1, \ldots, b_r \in \{\pm 1\}\) of random bits, and the derived random walk \(p_1 = b_1\), \(p_2 = p_1 + b_2\), \(\ldots\), \(p_r = p_{r-1} + b_r\), we consider the sequence \(a_1, \ldots, a_L\) w.h.p. containing \(p_1, \ldots, p_r\) as a subsequence. Denote the minimum length required by \(L\). We can prove that \(L = \Theta(r^{1.5})\):

- lower bound: \(t := 0.01r\) walks hits about \(tr\) points with about \(r^{-0.5}\) collision chance for each pair, so \(L > tr - t^2/r^{0.5} = r^{1.5}\).
- upper bound: repeat \([-r^{0.5}, \ldots, r^{0.5}]\) \(r\) times, since the random walk concentrates on this range.

Such a length-\(L\) sequence implies a length-\(L\) width-\(L\) ROBP with effective width 1 and amplification of \(r^{0.5}\) (the construction of the previously described ROBP): just run through the sequence and reject if the walk represented by input is not contained, i.e., detect those walk touching the \(\pm \sqrt{r}\) concentration boundary.

In the other direction, a length-\(n\) width-\(w\) ROBP for \(\delta\)-biased coins implies \(L = wn\) for \(r = \Theta(1/\delta^2)\), giving such lower bound: \[ \delta < n^{-1/3 - \epsilon} \implies w > 1/n\delta^3 > n^{3\epsilon} = n^{\Omega(1)}. \]

## Open Problem

- Whether the threshold remains when multiple passes to the coin stream is allowed?

## References

- [BGZ21] Mark Braverman, Sumegha Garg, and Or Zamir.
*Tight Space Complexity of the Coin Problem*. FOCS 2021 [ECCC TR21-083] - [BGW20] Mark Braverman, Sumegha Garg, and David Woodruff.
*The Coin Problem with Applications to Data Streams*. FOCS 2020 [ECCC TR20-139] - [BV10] Joshua Brody and Elad Verbin.
*The coin problem and pseudorandomness for branching programs*. FOCS 2010 [ACM DL] [Brody] - [Bop85] Ravi B. Boppana.
*Amplification of Probabilistic Boolean Formulas*. FOCS 1985 [IEEEXplore] - [DV97] Moshe Dubiner and Uri Zwick.
*Amplification by Read-Once Formulas*. SIAM Journal on Computing, 1997 [SIAM]