b'@techreport{Torben98,'b'\nTITLE = {Simpler and faster static {AC}\\${\\textasciicircum}0\\$ dictionaries},\nAUTHOR = {Hagerup, Torben},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-1998-1-001},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1998},\nDATE = {1998},\nABSTRACT = {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)$.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'