r/compsci • u/azurerazor • 15d ago

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

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

97% Upvoted

52 comments sorted by

91

u/cbarrick 15d 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.

64

u/stonerism 15d 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.

31

u/Timetraveller4k 14d ago

<Task failed successfully >

11

u/andrerav 14d 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?

21

u/blargh9001 14d 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 14d ago

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

2

u/TiredDr 13d ago

There are.

12

u/Mescallan 14d 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.

2

u/andrerav 14d ago

Thank you for clarifying!

2

u/JollyJoker3 14d 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.

10

u/cscottnet 14d ago

People's definition of "actual work" may vary.

Writing a quality paper for publication is hard.

-1

u/currentscurrents 14d ago

If a human found an algorithm for subquadratic 3-SUM and then had someone else do the writeup, there would be no question about which of them did the 'actual work'. Obviously it's the one who found the algorithm.

You just want to downplay the AI's contributions.

5

u/cscottnet 13d ago

I'm not doing either. I'm saying both made valuable contributions. In academia that's the only requirement for coauthorship.

3

u/GoldenMuscleGod 14d ago

It’s difficult to know what the Claude’s output looked like, but if we imagine it looked like just dumping the algorithm with a lean proof that it had the time constraints it has then the authors arguably did most of “the actual work.”

Claude produced the algorithm and showed it resolved an open question, the authors (with some amount of help from Claude) explain how the algorithm works and gave a more extensive description of what problems its ideas effectively resolve.

The authors explain it takes advantage of only needing to compute certain entries in matrices computed by Coppersmith’s algorithm and evaluating how to balance the cost of “calculating everything efficiently in advance” versus “only calculating what you need inefficiently” to get a result better than doing either on a case by case basis.

Maybe Claude already explained this clearly but understanding that that’s what’s going on is the real advancement, not just having an algorithm with impractical constants but improved exponents in its running time.

The authors at least say section 2 is their best attempt to present the algorithm accessibly and section 4 is their generalization to theory so you can compare the idea of the algorithm in 2 and the abstraction in 4 to see if you think the humans added value. (Though the humans are almost certainly responsible for 2 being as accessible as it is - who knows if Claude even mentioned Coppersmith’s algorithm in its version even though it seems to be based on exploiting its computational characteristics).

9

u/Dihedralman 14d ago

Wow that's less tokens than I would think. 

28

u/randomsubaccount 15d ago edited 14d 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 15d ago

What does .07 imply that .063 does not?

16

u/randomsubaccount 15d ago edited 15d 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.

66

u/Sezbeth 15d 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 14d 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

2

u/cloakrune 13d ago

Can I follow somewhere?

1

u/r0ze_at_reddit 13d ago

Yup, sent a DM

1

u/Vpharrish 13d ago

It sounds interesting, dm it to mee too!

1

u/Substantial_Photo312 13d ago

Could you DM IT to me too please? :)

1

u/andrew314159 12d ago

Me three please

1

u/PerpetualAceman 8d ago

Interesting, dm to me too

1

u/_The1DevinChance 14d ago

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

3

u/AQcjVsg 13d ago

we will have P=NP but in O(n^Tree(3))

4

u/justaRndy 13d ago

I mean, better than nothing, right?

7

u/ADisappointingLife 14d ago

Buddy, I haven't even managed to have a quadratic 3SUM, let alone a sub-quadratic one.

2

u/Mendoza2909 12d ago

True story, I had a problem I was trying to solve at work once that related to the 3sum problem. So I googled it and me and my colleague saw some images that we very much did not expect to see

10

u/Bangoga 15d 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.

10

u/Meliorus 14d ago

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

2

u/IEavan 14d ago edited 14d 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

1

u/SycamoreHots 14d ago

How large must n be before that asymptotic behavior is reached?

-14

u/Vanitas_Daemon 15d ago

I'm disappointed no one made a threesome joke.

10

u/doocheymama 15d ago

Grow up

4

u/jeffgerickson 14d ago

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

1

u/doocheymama 14d ago

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

1

u/Vanitas_Daemon 14d ago

Oh that's glorious.

-26

u/MyUsrNameWasTaken 15d ago

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

39

u/CrownLikeAGravestone 15d 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.

0

u/BrixtonTonaBrix 14d ago

You've said "now we know 3SUM isn't actually hard in the way we thought it was" and "it's about what that means for the rest of the field".

What does it mean for the rest of the field? Suppose that all (or at least some) O(n^2) problems are now O(n^1.9992) problems. What does that actually mean? Like, what actually changes? What do we do with it?

2

u/CrownLikeAGravestone 14d ago

Let's say I was really into making bows and arrows, and I wanted to shoot the highest-velocity arrow I could. Lots and lots of people try this, and we all find that with our best creative efforts we can get arrows arbitrarily close to the speed of sound but never higher.

We conjecture "hey maybe the speed of sound is the natural limit on arrow flight?". That makes a kind of intuitive sense; the speed of sound is the speed at which mechanical force propagates in some medium, a bow is a mechanical device for force transfer. We can't prove that the speed of sound is the upper limit but with all these bowyers trying and failing to break that limit, our confidence is pretty high.

Then along comes some strange guy with a really weird bow. It's got clockwork and fancy metals and the arrows are so thin you can barely see them, but we repeatedly confirm: it goes 1m/s over the speed of sound.

Does anyone want that bow? No! It's absurdly fragile and expensive, it'll never be practical for anything, and the cost to manufacture and fire it is eye-watering for a measly meter per second.

But the principle is what matters here, not the bow. There are two primary findings:

Firstly, we may be able to extend the techniques in this new bow to produce something even faster, and it opens up new solutions for all sorts of other engineers too.

Secondly, and more importantly, we have a proof that the assumed speed limit is not actually a limit. It was a plateau. We can go faster than the speed of sound, potentially a lot faster, we just need to figure out how to do so in a manner that actually makes sense.

That's the kind of result we're talking about here. Nobody cares about running some galactic algorithm very slightly faster on near-infinitely-large inputs. It's about the fact that it was technically possible in the first place.

0

u/BrixtonTonaBrix 14d ago

Two problems I see here. First, I don't see how confidence in a likely limit would suppress desire to break it, so I don't think the demo is motivating any work that wouldn't be done anyway. Why would they need proof? Who is the demo for?

Second, this strange guy turning up with their strange bow and talking in math and buzzing like a fridge and doing unintelligible and unenlightening demos is being an arse; if they don't and won't engage with the community the community has little chance of learning from or reproducing the strange bow. There's no rule that says the demo alone helps anyone else, and little evidence so far to suggest that'll change. Strange bow person isn't going to be a good teacher or collaborator. They charge crazy fees to talk at conferences and almost no one understands the content, and they're wearing a wire the entire time feeding everything you ask them to the nearest billionaire.

None of this points to a healthy and supported community that'll make progress on anything worth caring about (I give 0 shits about the fastest possible arrow within or without the metaphor). All of this points to someone desperately wanting some VC money and deciding that a strange bow is the most cost-effective hype available. Even if some real progress were to happen it would be by chance and in spite of strange bow person, because progress is not what this system is built to achieve.

In short: you paint a lovely optimistic picture, but if our goal is collective knowledge and betterment I think we need to zoom out a little and see this grift for what it is, because OpenAI is in no way interested in collective knowledge or betterment

1

u/CrownLikeAGravestone 13d ago

You seem more interested in telling me how awful OpenAI are than actually engaging with what I'm saying, so I'm going to bow out. Goodbye.

0

u/BrixtonTonaBrix 13d ago

I'm rejecting the scope of what you're saying on the grounds it's a waste of both our time, yes 

11

u/godofpumpkins 15d 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 15d ago

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

4

u/dMestra 15d ago

Either trolling or really really really dumb