Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
FOCS Conference 1986 Conference Paper
We describe two methods for obtaining lower bounds on the cost of accessing a sequence of nodes of a symmetrically ordered binary search tree, where rotations can be done on the tree. The bounds apply to offline as well as online algorithms.
FOCS Conference 1983 Conference Paper
A language L is random with respect to a given complexity class C if for all ′ ∈ C L and ′ disagree on half of all strings. It is known that for any complexity class there are recursive languages that are random with respect to that class. Here it is shown that there are tight space and time hierarchies of random languages, and that EXPTIME contains P-isomorphism classes containing only languages that are random with respect to polynomial-time computations. The technique used is extended to show that for any constructible bound on time or space it is possible to deterministically generate binary sequences that appear random to all prediction algorithms subject to the given resource bound. Furthermore, the generation of such a sequence requires only slightly more resources than the given bound.