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:

1. $$O(\log \log n)$$-memory streaming algorithm for $$\delta \gg n^{-1/3}$$ (recursive majority)
2. $$\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.

Essentially speaking, this is because every subprocedure has only one caller state $$s$$ on ROBP with effective width 1, which allows us to relocate the accepting/rejecting states to the corresponding successive states of $$s$$. If multiple caller states exist, we will need extra information to distinguish which caller we should relocate to.

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.

But what's its difference from the counting process?

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?
• [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]