Planar Reachability in Linear Space and Constant Time

We prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques ...

Given a pattern string of length m for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern ...

We show that a unit-cost RAM with a word length ofwbits can sortnintegers in the range 0 2w 1 inO(nloglogn) time for arbitraryw logn, a significant improvement over the bound ofO(nlogn) achieved by the fusion trees of Fredman and Willard. Provided thatw ...