Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

## Description

The emph{Coin Problem} is the following problem: a coin is given, which lands on head with probability either \$1/2 + eta\$ or \$1/2 - eta\$. We are given the outcome of \$n\$ independent tosses of this coin, and the goal is to guess which way the coin is biased, and to be correct with probability \$ge 2/3\$. When our computational model is unrestricted, the majority function is optimal, and succeeds when \$eta ge c /sqrt{n}\$ for a large enough constant \$c\$. The coin problem is open and interesting in models that cannot compute the majority function.

In this paper we study the coin problem in the model of emph{read-once width-\$w\$ branching programs}. We prove that in order to succeed in this model, \$eta\$ must be at least \$1/ (log n)^{Theta(w)}\$. For constant \$w\$ this is tight by considering the recursive tribes function.

We generalize this to a emph{Dice Problem}, where instead of independent tosses of a coin we are given independent tosses of one of two \$m\$-sided dice. We prove that if the distributions are too close, then the dice cannot be distinguished by a small-width read-once branching program.

We suggest one application for this kind of theorems: we prove that Nisan's Generator fools width-\$w\$ read-once emph{permutation} branching programs, using seed length \$O(w^4 log n log log n + log n log (1/eps))\$. For \$w=eps=Theta(1)\$, this seedlength is \$O(log n log log n)\$. The coin theorem and its relatives might have other connections to PRGs. This application is related to the independent, but chronologically-earlier, work of Braverman, Rao, Raz and Yehudayoff (which might be submitted to this FOCS).