
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Description
In this paper we study the coin problem in the model of emph{readonce 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 smallwidth readonce branching program.
We suggest one application for this kind of theorems: we prove that Nisan's Generator fools width$w$ readonce 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 chronologicallyearlier, work of Braverman, Rao, Raz and Yehudayoff (which might be submitted to this FOCS).