Hacker News Reader

Comment by kevinwang | Hacker News Reader

Wow, can anyone give the TCS community context on this? Would most people have thought these to be possible, to be impossible, or would most people not have thought about this before?

View on HN

Nobody thought this was possible.

3sum hard was colloquially considered to be >= n^2

It's an absolutely unbelievable result! (Personally, this is more meaningful to me than Navier Stokes and feels more surprising - not that an agent did it but the result itself is extremely surprising!)

Do you have any more detail on this? When I first saw the 3SUM result, it was accompanied with a comment something like "There is the obvious O(n^3) algorithm, and a pretty easy O(n^2) algorithm". I thought for about 15 seconds and came up with: put all the numbers in a hash table (O(n)). Search every pair of numbers (O(n^2)) and check if the negative value is in the table (O(1)). I checked Wikipedia and that is basically the simple version (though there are algorithms with a lower constant and lower storage).

But it seems strange that an algorithm that I can come up with in 15 seconds (and I'm not very good at this) is also optimal! It's more surprising that this can't be beat (or couldn't be beat). So there must be something more to the story.

Yes that’s the idea, these conjectures basically say “there’s no better algorithm than the naive/brute force one”. It’s like if P!=NP, then there’s no (asymptotically) better algorithm for SAT than naive backtracking search.

I don't really understand. The fact that, until now, no one's been able to come up with a better algorithm than the one everyone thinks of in 15s is what makes it an interesting conjecture.

It's made more tantalising by the fact that O(n^2) is so much larger than O(n) (the obvious lower bound needed to read the input), which suggests "room" for "something clever to do better".

It's the "Nobody thought this was possible" that I found curious. Yes, there is a lot of room between O(n) and O(n^2)! That's why it seems strange that it would be thought impossible.

But I guess it is just that people have been working on it for a long time with no progress, and so the thought was that there must be something especially hard about it. And, well, there is something comforting about round numbers, and so O(n^2) is something special, whereas if the O(n^1.9992) algorithm was known from the start I doubt anybody would have been surprised if O(n^1.9991) was possible.

It's not just that people have worked on it for a long time, it's that there are dozens of problems that are known to be 3sum hard and people have tried to make those as efficient as possible too!

Eg here's a paper with a bunch https://people.csail.mit.edu/virgi/6.1420/papers/gajovermars...

So every grad student who has thought about geometry problems will have spent more time than they're proud to admit thinking about better algorithms only to realize it's 3sum hard.

It's not just "people have thought about one problem a bunch" - the whole class has been wailed on to no avail

3SUM is (was?) one of the key conjectures in fine-grained complexity, mostly used to derive lower bounds for other problems. As such, most did not think a subquadratic algorithm was possible. Similar for APSP

But from what I understand this doesn't refute SETH, no?

No it does not.

> But from what I understand this doesn't refute SETH, no?

SETH: Strong Exponential Time Hypothesis

See https://en.wikipedia.org/w/index.php?title=Exponential_time_...

Reply on news.ycombinator.com