The random-query model and the memory-bounded coupon collector

Ran Raz, Wei Zhan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 x1, . . ., xn. In each time step, the branching program gets as an input a random index i ∈ {1, . . ., n}, together with the input variable xi (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) ≥ Ω(n2), where n is the number of different coupons.

Original languageEnglish (US)
Title of host publication11th Innovations in Theoretical Computer Science Conference, ITCS 2020
EditorsThomas Vidick
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771344
DOIs
StatePublished - Jan 2020
Event11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States
Duration: Jan 12 2020Jan 14 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume151
ISSN (Print)1868-8969

Conference

Conference11th Innovations in Theoretical Computer Science Conference, ITCS 2020
CountryUnited States
CitySeattle
Period1/12/201/14/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Branching programs
  • Random-query model
  • Time-space trade-offs

Fingerprint Dive into the research topics of 'The random-query model and the memory-bounded coupon collector'. Together they form a unique fingerprint.

  • Cite this

    Raz, R., & Zhan, W. (2020). The random-query model and the memory-bounded coupon collector. In T. Vidick (Ed.), 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 [20] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 151). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2020.20