Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TIME AND SPACE COMPLEXITY:
Reports tagged with Time and Space Complexity:
TR04-049 | 15th June 2004
Piotr Berman, Marek Karpinski, Yakov Nekrich

#### Optimal Trade-Off for Merkle Tree Traversal

We prove upper and lower bounds for computing Merkle tree
traversals, and display optimal trade-offs between time
and space complexity of that problem.

more >>>

TR04-118 | 21st December 2004
Marek Karpinski, Yakov Nekrich

#### A Note on Traversing Skew Merkle Trees

We consider the problem of traversing skew (unbalanced) Merkle
trees and design an algorithm for traversing a skew Merkle tree
in time O(log n/log t) and space O(log n (t/log t)), for any choice
of parameter t\geq 2.
This algorithm can be of special interest in situations when
more >>>

TR21-087 | 22nd June 2021
Uma Girish, Ran Raz

#### Eliminating Intermediate Measurements using Pseudorandom Generators

We show that quantum algorithms of time T and space $S \ge \log T$ with intermediate measurements can be simulated by quantum algorithms of time $T\cdot \mathrm{poly}(S)$ and space $O(S\cdot \log T)$ without intermediate measurements. The best simulations prior to this work required either $\Omega(T)$ space (by the deferred measurement ... more >>>

ISSN 1433-8092 | Imprint