Tight Space Complexity of the Coin Problem

Posted on Edited on

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?

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]