DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

                       Static Dictionaries on AC0 RAMs:                      
      Query time Theta(sqrt(log n/loglog n)) is necessary and sufficient     

                                Arne Andersson                               
                        Department of Computer Science                       
                               Lund University                               

                    Wednesday, March 20, 1996, at 10:15 AM                   
                               The Seminar Room                              


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, Soeren Riis, and Mikkel Thorup.


                                                               Joan F. Boyar