Aarhus University Seal / Aarhus Universitets segl

Static dictionaries on AC0 RAMs: query time (√log n/log log n) is necessary and sufficient

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
In this paper we consider solutions to the static dictionary problem on AC0 RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC0. Our main result is a tight upper and lower bound of θ(√log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2polylog n. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth Ω(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984)
Original languageEnglish
Title of host publication37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings.
Number of pages10
PublisherIEEE Computer Society Press
Publication year1996
Pages441-450
DOIs
Publication statusPublished - 1996
EventAnnual Symposium on Foundations of Computer Science - Burlington, VT, United States
Duration: 14 Oct 199616 Oct 1996
Conference number: 37

Conference

ConferenceAnnual Symposium on Foundations of Computer Science
Nummer37
LandUnited States
ByBurlington, VT
Periode14/10/199616/10/1996

See relations at Aarhus University Citationformats

ID: 21705753