From the 1 of 8 linked papers with an AI index.
7 papers · 1 filter
Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries
Guy E. Blelloch, Yang Hu, William Kuszmaul +2
The dynamic dictionary is a fundamental data structure that maintains a set of size (we assume ), supporting insertions, deletions and membership q…
Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space
Guy E. Blelloch, Yang Hu, William Kuszmaul +2
We show how to implement a dynamic array with symbols from a fixed alphabet , while supporting -time queries and updates, and using a total space of $$ \log \bin…
Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood
Yang Hu, William Kuszmaul, Jingxun Liang +3
The paper studies a smoothed version of quadratic probing for hash tables, comparing Robin Hood and anti‑Robin Hood insertion orders and showing that anti‑Robin Hood achieves logar…
Fast Concurrent Primitives Despite Contention
Michael A. Bender, Guy E. Blelloch, Martin Farach-Colton +4
We study the problem of constructing concurrent objects in a setting where processes run in parallel and interact through a shared memory that is subject to write contention. O…
Nearly Optimal Bounds for Stochastic Online Sorting
Yang Hu
In the online sorting problem, we have an array of cells, and receive a stream of items . When an item arrives, we need to immediately and irrev…
Static Retrieval Revisited: To Optimality and Beyond
Yang Hu, William Kuszmaul, Jingxun Liang +3
In the static retrieval problem, a data structure must answer retrieval queries mapping a set of keys in a universe to -bit values. Information-theoretically, retrieva…