Group:Complexity Group
Title: The Coin Problem,and Pseudorandomness for Branching Programs
Speaker: Elad Verbin Tsinghua university
Time: 2010-04-14 14:00-2010-04-14 15:00
Venue: FIT1-222

Abstract:

The "Coin Problem" is the following problem: a coin is given, which lands on head with probability either 1/2+beta or 1/2-beta. 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 >= 2/3. When our computational model is unrestricted, the majority function is optimal, and succeeds when beta >= 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 talk I will present results on the coin problem in the model of read-once width-w branching programs. We prove that in order to succeed in this model, beta must be at least 1/ (log n)^{Theta(w)}. For constant w this is tight by considering the recursive tribes function. I will show various generalizations and variants of this. The solution has two key steps: (i) proving that any branching program can be made "monotone" while not hurting its ability to solve the coin problem. (ii) proving that any monotone branching program is killed by a random restriction with appropriately-chosen parameter. Any function which is killed by random restrictions cannot solve the coin problem very well (for beta which depends on the parameter in the random restriction).

Finally, I will suggest one application for this kind of theorems: I'll show that Nisan's Generator eps-fools width-w read-once *permutation* branching programs, using seed length O(logn*loglogn) when eps and the width are both constant. I'll also show why we get this only for permutation branching programs, and what stops us from getting this for the non-permutation case.

We are very much looking for applications of the coin problem in other domains (e.g. streaming lower bounds), as well as other domains where the coin problem is interesting.

This is joint work with Joshua Brody.




Short Bio: