Undergraduate Disproves 40-Year-Old Conjecture, Invents New Kind of Hash Table

<i>&gt; Krapivin was not held back by the conventional wisdom for the simple reason that he was unaware of it. “I did this without knowing about Yao’s conjecture,” he said.</i><p>This idea resonates with me, especially in the context of modern physics. The extensive learning required to make advancements often means that one&#x27;s thinking is heavily influenced by established theories and teachings, potentially stifling true innovation.

I was hoping they&#x27;d have a discussion of the algorithm itself. Quanta is usually good about making these sorts of things approachable.<p>In any case, the full paper is here [1] if you don&#x27;t want to scroll through the Wired article.<p>[1] <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;2501.02305" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;2501.02305</a>

If my reading of the paper was correct, this kind of hash table is incredibly complicated to resize because resizing would invalidate all previously handed out pointers unless you only do chaining?<p>The other challenge is that computing N hash functions is quite expensive so in practice I think this ends up slower in real world terms despite the big-O speed up?<p>Does this actually end up beating open addressed hash tables? It seems more like a neat hypothetical CS result that wouldn’t have any actual real world application? That’s cool in and of itself but I’m curious if there’s any real world reason to do this.

original discussion: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=43002511">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=43002511</a>

Based on the last two convos I saw on this, I feel like there’s a simpler algorithm here waiting to break out.<p>Underneath this is a sort of b-tree scented data structure that avoids the bimodal distribution on insertion times, which is important for a concurrent hash table.

If it was his discovery, would be nice if they&#x27;d give him first author on the paper&#x27;s author list (Farach-Colton, Krapivin, Kuszmaul). Though I understand if the proofs were not done by him.

This article strongly reminded me of Heckle Diff, which was first published almost 47 years ago. <a href="https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;10.1145&#x2F;359460.359467" rel="nofollow">https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;10.1145&#x2F;359460.359467</a><p>The performance consideration Paul Heckle identified was in consideration of index access in arrays versus hash tables. Hash tables are accessed randomly, or pseudo-randomly, until the desired index is found where as indexes in an array are accessed in index order.

I wonder if there is a memory consumption tradeoff for this new data structure? Based on a few initial implementations I see in github, looks like it may be significant? Still a nice discovery.

I watched the video, but I didn&#x27;t understand why they create a &#x27;funnel&#x27; at each step. Why not create an equal size array? is it because it would take more memory?

Earlier: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=43002511">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=43002511</a>