2 citations · 2 across the 8 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…
cs.DS2024
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…