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

https://www.wired.com/story/undergraduate-upends-a-40-year-old-data-science-conjecture/

by robin_reala • 1 year ago

246 112 1 year ago

taylodl3• 1 year ago

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.

This idea resonates with me, especially in the context of modern physics. The extensive learning required to make advancements often means that one's thinking is heavily influenced by established theories and teachings, potentially stifling true innovation.

vincekerrazzi• 1 year ago

Potential digression here, this is why I absolutely insist on high performing software teams to have at least one junior. You need someone asking questions like this.

r00f• 1 year ago

Would it work in this case? Had he asked about this in a team, he would be told about the existing approach and that'd be it. I've been on the both sides, as junior questioning common practices and as senior answering such questions - and it always resulted in transfer of common knowledge, not some breakthrough.

I totally support searching for the new truths, but we must not forget why the phrase "do not roll your own crypto" exists. It is ok, or maybe it even MUST be done by students and researchers, but I am not so sure about juniors working on production systems. Still fine if you work in R&D department

socks• 1 year ago

unfortunately, I have a feeling that in the age of LLMs, this junior on the team will have no impetus to actually put in effort and _think_ about such a problem

gopher_space• 1 year ago

It’s nice to have someone around who doesn’t understand that I’ve given them hard work. Big, open ended tasks like “invent a photogrammetry pipeline”

KineticLensman• 1 year ago

Yes, just like evil geniuses should have their plans for world domination reviewed by a 5 year old

geodel• 1 year ago

I think a presence of even single senior can dampen the questioning part. So I prefer all junior team to make some big path breaking changes.

jhanschoo2• 1 year ago

Do you have a personal example that you can point to regarding modern physics?

mistercheph3• 1 year ago

Do you have an example of a meaningful breakthrough in that field in the last 25 years?

What's more likely, that we are nearing completion of understanding, or that our approach is misguided and in need of Newtonian revolution of method?

NotYourLawyer4• 1 year ago

There’s some truth to that. But there are also a LOT of “self-taught” cranks out there who think they’ve discovered an amazing new theoretical framework… but if they’d done any background reading, they’d know it’s been tried and didn’t work.

mistercheph3• 1 year ago

So what? Let them crank on, it's no less productive than most career researchers, collecting data on the 10,000th subdegree of some nested abstraction. (It is good to have some number of people doing that!) To me the two seem to actually be extremely similar behaviors except one is blessed by the church and the other is heterodoxy.

Thou shalt not inquire without passing through the blessed gates of wisdom and drinking from the fountain of holy knowledge!

jfengel• 1 year ago

All of the advances of modern physics were made by people who were well trained and well acquainted with the state of the art.

There is a myth that Einstein was an outsider. He had a degree in physics. He was working as a patent clerk because he couldn't find a job as a high school teacher, not because he didn't know physics.

gaugefield• 1 year ago

One of his earliest great works is one that indicated wrong in the foundational aspect of the theory, namely incompatibility with E&M Maxwell equations and Galilean Transformations and E&M equations not being invariant under those transformations. The principle of symmetry is one of the foundation issues in physics. He also had th wisdom of understanding of the physics of new transformation, Lorentz transformation, which we know today as Special Relativity.

Yes, of course he was well-trained and had the enough background, but also the problem at the time was the type of problem that was solvable (i.e. no limitation in terms of tech) and that required new framework with new understanding.

snarf21• 1 year ago

One question I had in college was if learning inhibits our ability to learn new things. We can gain knowledge but is that the same as learning? I'm not sure where the line sits between questioning and obstinance.

Looking back at Theranos, lots of "experts" (at Stanford, etc.) told her her idea was impossible given the small amount of blood but she convinced people she found a way. It was all a fraud but is there a way to do blood testing at that scale? Do we just need people to keep failing and see if anyone ever gets there? Should academia stick to things that aren't known to be "impossible"? I don't have any answers but find it interesting to contemplate.

andrewflnr6• 1 year ago

Picking Theranos as an example in favor of ignoring conventional wisdom is really a bold choice. I know there are better examples, based on actual results instead of wishful thinking.

plorkyeran• 1 year ago

Your example of a time where ignoring the "experts" was a good thing was a time when the experts were correct?

graemep• 1 year ago

Somewhat similar to Plank's principle:

"A new scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die and a new generation grows up that is familiar with it "

smithkl42• 1 year ago

Or more simply: "Science progresses one funeral at a time."

eviks4• 1 year ago

This is just a phrase in an article, there is no reason to believe it reflects the reality in any way. For example, the guy faced a sceptical advisor's response to his proposal. You could say "Krapivin was held back by the conventional scepticism of his boss" (which is a real thing vs the mythical power of conventional wisdom). Yet he wasn't.

beej71• 1 year ago

Reminds me of (I think) the PostIt note inventors saying that if they'd looked at the research ahead of time, they never would have even tried.

sitkack2• 1 year ago

That says more about the culture of giving up than of doing research.

Research can tell you immediately if something is possible, or that you need to do more research.

meifun• 1 year ago

This intrigues me, can you share more about this?

gowld• 1 year ago

https://www.post-it.com/3M/en_US/post-it/contact-us/about-us...

andrewflnr6• 1 year ago

Since people are getting a little squirrelly, I think it's important to point out that this discovery was only in contradiction with a conjecture, not something anyone pretended to prove. Conjectures exist to be falsified.

rmah• 1 year ago

If I may be so bold, it resonates (with you, with me, with most people) because the idea that one can make revolutionary discoveries that contradicts the status quo as an outsider is an inherently attractive idea. It scratches many emotional itches: tweaking the nose of "the man"; suspicion of institutions; being an unknown hero (before the discovery); discovering one's inherent, but unrecognized, greatness; and more.

But the reality of the matter is that for every Krapivin, there are thousands of other people who tried but did not. And more importantly, there are hundreds of others who did the work, gained the foundational knowledge, and THEN made a discovery that changed how we think about the world even if only a tiny bit. While it's not as romantic, it's the way reality works. Mostly.

It sounds like Krapivin is continuing his education. And hopefully his hard work will hone his brilliance and help him to make even more discoveries in the future.

campbel• 1 year ago

because the idea that one can make revolutionary discoveries that contradicts the status quo as an outsider is an inherently attractive idea

This might be satisfying if you have a grievance with the "institution" but to OP's point its also interesting because we often limit our areas of exploration to what is conventionally accepted. If you are ignorant of convention you are more likely to retread ground, but less likely to be bounded by it. As you say, conventional wisdom is conventional because its pretty dang good, so this doesn't often pay off.

Pxtl2• 1 year ago

Yeah, everybody wants to be the Karate Kid who binged karate studies in one montage and then won the tournament instead of training in the dojo for years and still having to cheat to come close to winning (and still failing) like the chumps at Cobra Kai.

casey2• 1 year ago

This exact thread was posted the last time this article was posted.

Is this site all bots. Hello? any real humans?!?!

forbiddenvoid2• 1 year ago

We can have both. I think we need both. Some problems are better suited to solutions coming from outsiders. Most are not. We don't know which are which.

SirYandi• 1 year ago

I find that thought reassuring. There is less of a gap between oneself and the greats than one might think.

bloqs2• 1 year ago

It resonates because of dopamine, and little else

etchalon• 1 year ago

https://youtu.be/11lPhMSulSU?si=Lqi274EhmzM7nTgB

viccis• 1 year ago

Martha Argerich has a similar anecdote when it came to learning a very difficult piano piece. Ravel's Gaspard de la nuit is notoriously difficult, even for accomplished pianists. She learned it (along with another tough one) in 5 days because her teacher told her to learn it. She claims that she was helped by the fact that she was unaware that it was supposed to be difficult.

hullo• 1 year ago

original discussion: https://news.ycombinator.com/item?id=43002511

keybored• 1 year ago

Top comment there: https://news.ycombinator.com/item?id=43005231

Second-to-top comment here: https://news.ycombinator.com/item?id=43388872

Shows the wide range of ideas we produce here.

mNovak2• 1 year ago

I was hoping they'd have a discussion of the algorithm itself. Quanta is usually good about making these sorts of things approachable.

In any case, the full paper is here [1] if you don't want to scroll through the Wired article.

[1] https://arxiv.org/abs/2501.02305

antognini• 1 year ago

Quanta did have an article about this discovery: https://www.quantamagazine.org/undergraduate-upends-a-40-yea...

rolandog• 1 year ago

Related HN discussion:

https://news.ycombinator.com/item?id=43002511

mNovak2• 1 year ago

Right, the Wired article is just a 1:1 reprint of the Quanta article. Both lack a substantive description of the algorithms in question

vlovich1232• 1 year ago

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?

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?

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.

hrdwdmrbl• 1 year ago

Likely why the article said that it wouldn’t lead to any immediate applications.

Cause from the headline, one would get all excited about the applications

ForTheKidz2• 1 year ago

Still worth it for situations where you can memoize hashes and reuse them. Basically, any situation where you want to intern strings.

augusto-moura• 1 year ago

Also worth it for the cases were you already know the maximum size for the table.

vlovich1232• 1 year ago

You realize that the number of hashes you have to memoize is variable and unknown ahead of time? And depending on the key, you’re adding a decent amount of overhead on memoization vs just computing the hash on the fly?

I’m going to go ahead and challenge you to actually try implementing this hash table and use it for anything where a normal highly optimized hash table won’t beat this (eg try to beat hashbrown from rust / abseil swisstable in c++)

diyseguy• 1 year ago

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.

jsbg• 1 year ago

what makes the new memory consumption significant? from the paper they break the initial array into log(n) arrays of size 1, 2, 4, 8...

herf• 1 year ago

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

ziddoap2• 1 year ago

I believe alphabetical is the norm in computer science, is it not?

treefarmer• 1 year ago

It is not, other than sometimes in the case of equal contribution. The first and sometimes second authors are the most important, and the last author is often the advisor/senior researcher supervising the work.

tylerhou• 1 year ago

Alphabetical is the norm in algorithms theory. It is not the norm in other subfields that I can think of, even theoretical fields like programming language theory.

hinkley• 1 year ago

Based on the last two convos I saw on this, I feel like there’s a simpler algorithm here waiting to break out.

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.

austin-cheney• 1 year ago

This article strongly reminded me of Heckle Diff, which was first published almost 47 years ago. https://dl.acm.org/doi/10.1145/359460.359467

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.

yencabulator• 1 year ago

Earlier: https://news.ycombinator.com/item?id=43002511

avinassh• 1 year ago

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

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

Related Stories