Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TIME-SPACE TRADE-OFFS:
Reports tagged with time-space trade-offs:
TR19-162 | 15th November 2019
Ran Raz, Wei Zhan

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

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,\ldots,x_n$. In each time step, the branching program gets as an input a random index $i \in \{1,\ldots,n\}$, together with the input variable $x_i$ (rather than querying an ... more >>>




ISSN 1433-8092 | Imprint