Remix.run Logo
▲ kevinwang 5 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?

▲wrsh07 4 hours ago | parent | next [-]

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

▲remywang 4 hours ago | parent | prev [-]

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

▲sigbottle 3 hours ago | parent [-]

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

▲aleph_minus_one an hour ago | parent | next [-]

> 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_...

▲p11p 3 hours ago | parent | prev [-]

No it does not.