Breakthrough Tracker record
Optimal Bounds for Open Addressing Without Reordering
The authors constructed open-addressed hash tables with better-than-expected search bounds, disproving the central conjecture in Andrew Yao's “Uniform Hashing Is Optimal.” They also proved matching lower bounds for the models studied.
← Back to the filtered Breakthrough Tracker
- Stable ID
open-addressing-yao-counterexample-2024- Revision
open-addressing-yao-counterexample-2024.v1- Field
- Computer Science · Data structures, hashing and combinatorics
- Evidence
- Tier 1 · Peer reviewed: Yes
- Record state
- Current · Disproof by counterexample; verified conference result
- Last checked
AI role
No AI assistance was disclosed in the paper or linked reporting.
Record details
- Problem or result
- Expected search and insertion costs in open-addressed hash tables without reordering
- Authors
- Martín Farach-Colton, Andrew Krapivin and William Kuszmaul
- Institutions
- New York University, University of Cambridge and Carnegie Mellon University
- Result date
- FOCS 2024; arXiv version January 4, 2025
Why it matters
The paper replaces a presumed 40-year-old barrier for one of computer science's most basic data structures with optimal bounds.
Limits
The result concerns a defined open-addressing model without reordering. It does not show that every real-world hash-table implementation should be replaced, and immediate engineering performance was not demonstrated.
Sources
- Primary: Primary paper on arXiv
- Primary: IEEE FOCS 2024 proceedings record
- Independent: Quanta Magazine explanation
Correction and revision history
- Initial entry.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.