Abstract (Arne Andersson)

In this paper we consider solutions to the static dictionary problem on AC0 RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC0. Our main result is a tight upper and lower bound of Theta(sqrt(log n/loglog n)) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2^(polylog n).

Several variations of this bound is also obtained, including tight upper and lower bound on the space if the query time must be constant, general (but not tight) time-space tradeoffs, and bounds valid for non-AC0 RAMs if the execution time of an instruction is measured as the minimal depth of a polynomially sized unbounded fan-in circuit computing the operation. As an example of the latter, we show that any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth Omega(log w/loglog w), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the solution of Fredman, Komlos and Szemeredi achieving these bounds.

One of the non-dictionary related consequences of our techniques is a randomized O(n(loglog n)^2) AC0 sorting algorithm using linear space. This is the first linear space AC0 algorithm beating the information theoretic lower bound of Omega(n log n).

This is joint work with Peter Bro Miltersen, Søren Riis, and Mikkel Thorup.


Last modified: April 15, 1996.
Kim Skak Larsen (kslarsen@imada.sdu.dk)