Piotr Berman, Marek Karpinski, Yakov Nekrich

We prove upper and lower bounds for computing Merkle tree

traversals, and display optimal trade-offs between time

and space complexity of that problem.

Marek Karpinski, Yakov Nekrich

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

Uma Girish, Ran Raz

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