4 citations · 8 across the 31 of their papers we have counts for
6 papers · 1 filter
Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
William Kuszmaul, Aaron Putterman, Tingqiang Xu +2
Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four sett…
Tight Bounds for Classical Open Addressing
Michael A. Bender, William Kuszmaul, Renfei Zhou
We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to , while also supporting expected-time queri…
A Nearly Quadratic Improvement for Memory Reallocation
Martin Farach-Colton, William Kuszmaul, Nathan Sheffield +1
In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the…
Scheduling Jobs with Work-Inefficient Parallel Solutions
William Kuszmaul, Alek Westover
This paper introduces the \emph{serial-parallel decision problem}. Consider an online scheduler that receives a series of tasks, where each task has both a parallel and a serial im…
Nearly Optimal List Labeling
Michael A. Bender, Alex Conway, Martín Farach-Colton +4
The list-labeling problem captures the basic task of storing a dynamically changing set of up to elements in sorted order in an array of size . The goal is to…
Layered List Labeling
Michael A. Bender, Alex Conway, Martin Farach-Colton +2
The list-labeling problem is one of the most basic and well-studied algorithmic primitives in data structures, with an extensive literature spanning upper bounds, lower bounds, and…