# Item

ITEM ACTIONSEXPORT

Released

Report

#### Simpler and faster static AC$^0$ dictionaries

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

MPI-I-98-1-001.pdf

(Any fulltext), 192KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Hagerup, T.(1998). *Simpler and faster static AC$^0$ dictionaries*
(MPI-I-1998-1-001). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-9A0E-5

##### Abstract

We consider the static dictionary problem of using
$O(n)$ $w$-bit words to store $n$ $w$-bit keys for
fast retrieval on a $w$-bit \ACz\ RAM, i.e., on a
RAM with a word length of $w$ bits whose
instruction set is arbitrary, except that each instruction
must be realizable through an unbounded-fanin circuit
of constant depth and $w^{O(1)}$ size, and that the
instruction set must be finite and independent of the
keys stored.
We improve the best known upper bounds
for moderate values of~$w$ relative to $n$.
If ${w/{\log n}}=(\log\log n)^{O(1)}$,
query time $(\log\log\log n)^{O(1)}$ is achieved, and if
additionally ${w/{\log n}}\ge(\log\log n)^{1+\epsilon}$
for some fixed $\epsilon>0$, the query time
is constant.
For both of these special cases, the best previous
upper bound was $O(\log\log n)$.