MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys


Simpler and faster static AC$^0$ dictionaries

Hagerup, Torben

January 1998, 13 pages.

Status: available - back from printing

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)$.

  • Attachement: ATT8RLX8 (179 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Hagerup, Torben},
  TITLE = {Simpler and faster static AC$^0$ dictionaries},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-98-1-001},
  MONTH = {January},
  YEAR = {1998},
  ISSN = {0946-011X},