Public
- Public
- Network
- Groups
- Featured
- Popular
- People

Conversation

Notices

Embed this notice
Klara, continued (klara@wandering.shop)'s status on Monday, 17-Mar-2025 06:22:21 JST Klara, continued

Holy shit: https://www.wired.com/story/undergraduate-upends-a-40-year-old-data-science-conjecture/
For the non-programmers: hash tables are one of those things you learn about in your first year as a CS student, and very likely in your first CS class. Not something you expect to read about conjecture-breaking, complexity-bounds-changing new implementations of.
Full paper: https://arxiv.org/abs/2501.02305
In conversation Monday, 17-Mar-2025 06:22:21 JST from wandering.shop permalink
Attachments
1. Untitled attachment
2. Domain not in remote thumbnail source whitelist: arxiv.org
  
  Optimal Bounds for Open Addressing Without Reordering
  
  In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper ``Uniform Hashing is Optimal''. All of our results come with matching lower bounds.

Feeds