Addressing a problem of Fredman and Willard, we implement fusion trees
in deterministic linear space using AC^o instructions only.
More precisely, we show that a subset of {0,...,2^(w-1)} of size n
can be maintained using linear space under insertion, deletion,
predecessor, and successor queries, with O(log n/loglog n) amortized
time per operation on a RAM with word size w, where the only computational
instructions allowed on the RAM are fuinctions in AC^0. The AC^0
instructions used are not all available on today's computers.
Full paper (postscript)
Full paper (pdf)