We study a new model of space-bounded computation, the {\it random-query} model. The model is based on a branching-program over input variables x 1 x n . In each time step, the branching program gets as an input a random index i 1 n , together with the input variable x i (rather than querying an input variable of its choice, as in the case of a standard (oblivious) branching program). We motivate the new model in various ways and study time-space tradeoff lower bounds in this model.

Our main technical result is a quadratic time-space lower bound for zero-error computations in the random-query model, for XOR, Majority and many other functions. More precisely, a zero-error computation is a computation that stops with high probability and such that conditioning on the event that the computation stopped, the output is correct with probability~1. We prove that for any Boolean function f : 0 1 n 0 1 , with sensitivity k , any zero-error computation with time T and space S , satisfies T ( S + log n ) ( n k ) . We note that the best time-space lower bounds for standard oblivious branching programs are only slightly super linear and improving these bounds is an important long-standing open problem.

To prove our results, we study a memory-bounded variant of the coupon-collector problem that seems to us of independent interest and to the best of our knowledge has not been studied before. We consider a zero-error version of the coupon-collector problem. In this problem, the coupon-collector could explicitly choose to stop when he/she is sure with zero-error that all coupons have already been collected. We prove that any zero-error coupon-collector that stops with high probability in time T , and uses space S , satisfies T ( S + log n ) ( n 2 ) , where n is the number of different coupons.