Abstract
We study a new model of spacebounded computation, the randomquery model. The model is based on a branchingprogram 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 timespace tradeoff lower bounds in this model.
Our main technical result is a quadratic timespace lower bound for zeroerror computations in the randomquery model, for XOR, Majority and many other functions. More precisely, a zeroerror 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 zeroerror computation with time T and space S, satisfies T ⋅ (S+log n) ≥ Ω(n⋅k). We note that the best timespace lower bounds for standard oblivious branching programs are only slightly super linear and improving these bounds is an important longstanding open problem.
To prove our results, we study a memorybounded variant of the couponcollector problem that seems to us of independent interest and to the best of our knowledge has not been studied before. We consider a zeroerror version of the couponcollector problem. In this problem, the couponcollector could explicitly choose to stop when he/she is sure with zeroerror that all coupons have already been collected. We prove that any zeroerror couponcollector 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.
BibTeX  Entry
@InProceedings{raz_et_al:LIPIcs:2020:11705,
author = {Ran Raz and Wei Zhan},
title = {{The RandomQuery Model and the MemoryBounded Coupon Collector}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {20:120:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11705},
URN = {urn:nbn:de:0030drops117053},
doi = {10.4230/LIPIcs.ITCS.2020.20},
annote = {Keywords: randomquery model, timespace tradeoffs, branching programs}
}
Keywords: 

randomquery model, timespace tradeoffs, branching programs 
Collection: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020) 
Issue Date: 

2020 
Date of publication: 

06.01.2020 