Skip to main content

The Random-Query Model and the Memory-Bounded Coupon Collector

Author(s): Raz, Ran; Zhan, Wei

To refer to this page use:
Abstract: We study a new model of space-bounded computation, the 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.
Publication Date: 2020
Citation: Raz, Ran, and Wei Zhan. "The Random-Query Model and the Memory-Bounded Coupon Collector." In 11th Innovations in Theoretical Computer Science Conference (ITCS) 151 (2020): pp. 20:1-20:11. doi:10.4230/LIPIcs.ITCS.2020.20
DOI: 10.4230/LIPIcs.ITCS.2020.20
ISSN: 1868-8969
Pages: 20:1 - 20:11
Type of Material: Conference Article
Journal/Proceeding Title: 11th Innovations in Theoretical Computer Science Conference (ITCS)
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.