2026-08-01T05:06:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20247 2024-07-02T07:52:53Z ddc:004 open_access

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing Larsen, Kasper Green Pagh, Rasmus Persiano, Giuseppe Pitassi, Toniann Yeo, Kevin Zamir, Or non-adaptive cell probe dictionary hashing We present a simple and provably optimal non-adaptive cell probe data structure for the static dictionary problem. Our data structure supports storing a set of n key-value pairs from [u]× [u] using s words of space and answering key lookup queries in t = O(lg(u/n)/lg(s/n)) non-adaptive probes. This generalizes a solution to the membership problem (i.e., where no values are associated with keys) due to Buhrman et al. We also present matching lower bounds for the non-adaptive static membership problem in the deterministic setting. Our lower bound implies that both our dictionary algorithm and the preceding membership algorithm are optimal, and in particular that there is an inherent complexity gap in these problems between no adaptivity and one round of adaptivity (with which hashing-based algorithms solve these problems in constant time). Using the ideas underlying our data structure, we also obtain the first implementation of a n-wise independent family of hash functions with optimal evaluation time in the cell probe model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kasper Green Larsen and Rasmus Pagh and Giuseppe Persiano and Toniann Pitassi and Kevin Yeo and Or Zamir 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.104 urn:nbn:de:0030-drops-202471 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.104 eng https://creativecommons.org/licenses/by/4.0/legalcode