Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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 >>>

TR23-096 | 28th June 2023
Huacheng Yu, Wei Zhan

Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions

We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of $n$ elements in $[n]$, outputs $O(n)$ elements, such that:

- There exists a randomized oblivious algorithm with space $O(\log n)$, time $O(n\log n)$ ... more >>>

ISSN 1433-8092 | Imprint