Fusion trees can be implemented with AC0 instructions.

• 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.

Nyckelord

fusion trees

AC0 instructions

models of computation

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)