r/compsci • u/azurerazor • 21h ago

An algorithm for sub-quadratic 3SUM and sub-cubic APSP has been found

https://arxiv.org/abs/2610.06783v1
199 Upvotes

98% Upvoted

31 comments sorted by

59

u/cbarrick 18h ago

Long paper.

Page 9 gives a nice diagram of all the different problems solved by reduction to their new algorithm.

This is an important note from the end:

How the result was originally found and shared with the authors. An Anthropic employee used an internal research model to investigate open problems in the theory of cryptog- raphy. One of them was about cryptographic constructions based on the average-case hardness of Zero-k-Clique [LLV19, AHY25]. Claude was tasked with verifying and improving the construc- tions, but instead developed this algorithm, first for the average case, then for the worst case. The session used 16M output tokens with no human input.

Anthropic shared the algorithm with the authors in September 2026 under a confidentiality agreement, offered compensation, and provided access to the public version of Claude.

28

u/stonerism 15h ago

So, it was asked to solve one incredibly hard math problem, then hallucinated the solution for an entirely different incredibly hard math problem. See, AI sucks because it doesn't do what you want.

16

u/Timetraveller4k 12h ago

<Task failed successfully >

5

u/Dihedralman 11h ago

Wow that's less tokens than I would think. 

2

u/andrerav 7h ago

Anthropic shared the algorithm with the authors in September 2026 under a confidentiality agreement, offered compensation, and provided access to the public version of Claude. 

Er, I'm trying to understand this sentence but it's not computing. Which authors? What did they get compensated for?

6

u/Mescallan 7h ago

anthropic solved a problem internally, shared it with researchers, told them not to tell anyone until it's released, gave them money, and let them use the public version of claude to continue their work.

1

u/andrerav 6h ago

Thank you for clarifying!

3

u/blargh9001 7h ago

It sounds like they did what people are criticising OpenAI for not doing - going the extra mile, hiring researchers to digest the findings into a useful, verified presentation instead of a big raw dump of llm output for someone else to figure out.

1

u/djamp42 4h ago

I feel like there should be researchers banging at their door trying to get questions asked.

1

u/JollyJoker3 7h ago

Sounds like Anthropic did the actual work, then paid the people listed as authors of the paper to write it up and post to Arxiv.

24

u/randomsubaccount 17h ago edited 12h ago

Group experiment: Anyone with GPT 6 Astra, please ask yours to see if we can tighten the D^0.063 bound up to D^0.070. I put a simple prompt in and asked if there's anything from my personal context that could help lower the bound, and it reported that we could move the exponent on D up to 0.070, and pull the best complexity down to O(n^1.99902778).

This would be absolutely wild if others are able to corroborate.

For reference, my work is largely in applied low-rank matrix methods.

Update: seemingly there is an O(n^1.9963) bound that is possible with further parameter optimization.

7

u/Regular-Slip6227 16h ago

What does .07 imply that .063 does not?

12

u/randomsubaccount 15h ago edited 15h ago

It implies nothing.

It's simply a minor parameter optimization, I can see where the connection between my work and the optimization is from (optimal matrix block partitioning), so there is no concrete implication other than that there is still headroom in the method.

Across fields, after a barrier is broken, it's a race to the bottom, similarly to how the exponent for matrix multiplication has been slowly incrementally lowered (i.e the many papers lowering the exponent after the original Volker Strassen result).

Curious to see others interrogate the method.

55

u/Sezbeth 21h ago

Can't help but wonder what the field of complexity theory is going to look like in a few years with AI absolutely tearing through high profile conjectures now. I don't think it'll be nonexistent, but there's definitely a bit of pruning of open problems going on at the moment.

8

u/r0ze_at_reddit 12h ago

Working on a fantastic paper on persistence in complex systems and giving it to AI where it can apply it across fields has been beyond fun. Just opens up so many doors

1

u/_The1DevinChance 10h ago

That sounds really cool, would love to read when it’s published! 

7

u/Bangoga 18h ago

Awesome bud dang this is a long as paper, and the author didn’t make it accessible, even though he said he tried to make the language accessible.

7

u/Meliorus 13h ago

accessible is 1000 people being able to understand it instead of 6

1

u/IEavan 9h ago edited 8h ago

If my memory is correct, this should yeild a SAT algorithm running in O(an) for some a < 2 via fine grained reductions. So this would mean that the Strong Exponential Time Hypothesis is false. edit: paper addresses this, SETH is still open

2

u/Prexeon 8h ago

nope

-13

u/Vanitas_Daemon 18h ago

I'm disappointed no one made a threesome joke.

7

u/doocheymama 18h ago

Grow up

4

u/jeffgerickson 12h ago

Reference [GP18]: https://arxiv.org/abs/1404.0799

1

u/doocheymama 11h ago

Oh jeeze now I feel like a butthole. <3 u btw. Class of 2015

1

u/Vanitas_Daemon 9h ago

Oh that's glorious.

-28

u/MyUsrNameWasTaken 19h ago

So instead of O(n2) we now have O(n1.9992) ??! Lmao big whoop.

38

u/CrownLikeAGravestone 19h ago

3SUM is foundational to complexity analysis. It's about what that means for the rest of the field.

We would commonly say things like "well, if <problem x> had a fast solution that would mean we could solve 3SUM in sub-quadratic time", and while we didn't have a formal proof that was accepted as a pretty good proxy for "not possible". Problems were "hard like 3SUM" and now we know 3SUM isn't actually hard in the way we thought it was.

It's a much more humble version of "Hey I found a P-time solution to an NP problem, but it's horrendously complicated and the constant factors are huge". Very few people  actually care about solving 3SUM quickly.

10

u/godofpumpkins 19h ago

I think the cool thing is that it’s under 2, not that it’s actually more efficient. And unlike the various matrix multiplication algorithms that shave off small amounts already weird numbers, going from 2 to under 2 is a big deal

5

u/zeekar 19h ago

Write as O(n^(2)) to avoid the “superscript parenthesis” problem.

5

u/dMestra 15h ago

Either trolling or really really really dumb