← Back to context

Comment by kevinwang

7 hours ago

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?

6 comments

kevinwang

Reply
wrsh07  6 hours ago

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!)

  • SyzygyRhythm  1 hour ago

    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.

remywang  6 hours ago

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