de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

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

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

1998-1-001
(beliebiger Volltext), 10KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

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

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