(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)
In this paper we consider solutions to the static dictionary problem
on AC^0 RAMs, i.e. random access machines where the only restriction
on the finite instruction set is that all computational instructions are
in AC^0. 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 result are also obtained.
Among others, we show a tradeoff between time and circuit depth
under the unit-cost assumption: 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 perfect hashing scheme by Fredman,
Komlos and Szemeredi.