Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with random-query model:
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 >>>

TR23-084 | 31st May 2023
Itai Dinur

Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model

The random-query model was introduced by Raz and Zhan at ITCS 2020 as a new model of space-bounded computation. In this model, a branching program of length $T$ and width $2^{S}$ attempts to compute a function $f:\{0,1\}^n \rightarrow \{0,1 \}$. However, instead of receiving direct access to the input bits ... more >>>

ISSN 1433-8092 | Imprint