Skip to main content

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

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1tz5p
Full metadata record
DC FieldValueLanguage
dc.contributor.authorRaz, Ran-
dc.contributor.authorZhan, Wei-
dc.date.accessioned2021-10-08T19:45:15Z-
dc.date.available2021-10-08T19:45:15Z-
dc.date.issued2020en_US
dc.identifier.citationRaz, 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.20en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1tz5p-
dc.description.abstractWe 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.en_US
dc.format.extent20:1 - 20:11en_US
dc.language.isoen_USen_US
dc.relation.ispartof11th Innovations in Theoretical Computer Science Conference (ITCS)en_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleThe Random-Query Model and the Memory-Bounded Coupon Collectoren_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.ITCS.2020.20-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
RandomQueryModelMemoryBoundCouponCollector.pdf429.73 kBAdobe PDFView/Download


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