alt Hacker NewsWow, 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?
Replies
remywang • today at 5:30 PM
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
➕ show 1 reply
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!)