A week has passed since Josh and I posted our write-up on the arXiv, and I decided to write a few things.

Much was said about our write-up. Some were excited, others enraged. Most everyone was scared. 

What does our write-up do? We were given a proof generated by an internal Anthropic model. 
The proof invented parts that were not necessary to invent and could have just been cited. We fixed this. The proof invoked unnecessary algebra language. We fixed this.
The proof did a lot of extra work to get deterministic algorithms for 3SUM and APSP. We fixed this by a simple deterministic reduction. The proof was not readable for a non-expert. 
We strived hard to fix this. The proof omitted many citations. We tried hard to fix this. We also strengthened the proof to solve a potentially harder problem, online set disjointness. We explained the relevant prior literature and we attempted to soften the blow that this proof would throw at our field.

Did we come up with the proof? No! We said so on the first page. 

We were explicitly contacted to look at this proof while others were not. This made some people sad and angry. Were we the right people to write the exposition and improvements? We certainly were among a subset of people who could have written it. What expertise was needed: (1) expertise in fine-grained complexity (I believe this checkmark is checked.), and (2) expertise in matrix multiplication algorithms (Arguably this checkmark is also checked.)

Could someone else have done a better job? Maybe, probably, who knows? I think that more people should write their own expositions of this result (and any result that an LLM gives us): we need to understand the ramifications as much as we can from as many viewpoints as possible. Some new expositions have started appearing (see e.g., https://eccc.weizmann.ac.il/report/2026/247/ which was also AI assisted).

I want to partially address a grave concern that many had raised: What are we to do when companies have such powerful internal models that can come up with these proofs? How can we compete? I cannot promise to assuage your fears (or my own). Who knows how things will unravel in a few months time. Let us see, discuss and prepare.

However, in our particular case (showing that Exact Triangle, 3SUM and APSP have faster algorithms) I claim that the internal model was unnecessary. We could have (even quickly!) proven the result without it. 

Several people in our community were extremely close to this particular result and the ONLY reason Claude could have come up with this is because of all of our work and intuitions. To prove this to you, I will tell you of an experiment I ran. Let me first explain the context.

When I first saw Claude's proof I must admit that I got quite mad at myself. 

Why? 
In 2019, van den Brand, Nanongkai, and Saranurak posed their hinted OMV conjectures. I was completely convinced that these conjectures were false! I formulated a simple approach to refute them and told many of my students that the conjectures are false and this approach will prove it. I tried the approach on the Coppersmith-Winograd tensors and it did not work. Nevertheless I kept telling my students about the approach. In 2022-2023 one of my PhD students, Shyan Akmal, believed that my approach could work and tried it on a few more tensors. It did not work with them, but Shyan wrote up his attempts and I have had his untouched notes since March 2023. 

Anyway, this approach that Shyan and I tried is exactly the approach that Claude used to solve the masked lopsided matrix product and (via known reductions) 3SUM and APSP. And in fact, we were 2 simple prompts to Claude Opus 5.5 or Fable 5.1 away from refuting 3SUM and APSP.

Here are the prompts:

(**prompt 1 **) [attach Shyan's notes with our approach, Coppersmith's 1982 paper and van den Brand, Nanongkai and Saranurak's paper defining the hinted OMV conjectures] Use the approach in the first file together with one of the two tensors in the second file to refute the conjectures in the third file. Don't use the internet and do not use any other chats we have had (I have disabled this in the settings too). 

--> Here Fable 5.1 returned a refutation after 19min 44secs, Opus 5.5 in 27min 1sec

(** prompt 2**)
Ok, now consider the following all edge sparse triangle problem in the rectangular regime: given a tripartite graph where two parts A and B have size n, part C has size n^tau for small tau>0. The edges between A and C and B and C can be arbitrary and these parts can be dense. There are at most O(n^{2-tau/2}) edges between A and B. We want to compute for each edge (a,b) with a in A and b in B whether there is a c in C such that a,b,c form a triangle in the graph. Can use the same approach as above to give an O(n^{2-eps}) time algorithm for this problem for some constant eps>0 depending on tau, for some small value of tau? Again don't use the internet.

--> Here Fable 5.1 returned a subquadratic algorithm after 30min 44sec, Opus 5.5 after about 45min (this is just an estimate since the Claude client didn't report the time) 

(**after the first 2 prompts we are actually done due to the known reductions but I had it run prompt 3 as follows**)
[attach Chan-Xu's paper on simple reductions from exact triangle] Now look at the reductions in this paper from exact triangle to all edge sparse triangles. You can see that it also works for the rectangular version that you can now solve. Can you conclude that you have a truly subcubic time algorithm for exact triangle and hence refute the 3sum and apsp hypotheses? Again don't use the internet or any of our other chats.

--> Both Fable 5.1 and Opus 5.5 succeeded in 10min or so but doubted their findings because the result would be crazy... As I mentioned that this prompt was unnecessary, because we have known for a while that this version of All Edge Sparse Triangle, also known as offline set disjointness, solves Exact Triangle, 3SUM [since Patrascu's 2010 paper!], and APSP.


I only ran a single run on Fable 5.1 and Opus 5.5 each. One can try to replicate it with multiple runs, and I have no doubt that it would succeed over and over.

Now, I decided to check if Shyan's manuscript was useful at all, so I ran another experiment on both Fable 5.1 and Opus 5.5, asking them to refute the hinted omv conjectures without supplying them with Shyan's file. Here's the prompt:

(**prompt 1 **) [attach Coppersmith's 1982 paper and van den Brand, Nanongkai, and Saranurak's paper defining the hinted OMV conjectures] Use one of the two tensors in the first file to refute the conjectures in the second file. Don't use the internet and do not use any other chats we have had (I have disabled this in the settings too).

--> Neither Fable 5.1 nor Opus 5.5 could refute the conjectures without the hint of our approach. I ran three tries each. E.g., in one run Fable 5.1's first sentence was "I spent a long time trying to make this work, and I can’t give you a refutation — and I don’t think one exists along this route."


Now this tells me that our 2023 write-up was useful. The prompts revealed no extra information beyond our write-up and Coppersmith's paper which we knew about and which was used in prior work on APSP. I think that this means that we were about 1 Claude-hour away from the result.

But.. neither Shyan nor I had been using LLMs tools for research. (I only started using them recently after seeing this paper https://arxiv.org/abs/2606.25887 in which some friends and colleagues, including my former student Yinzhan Xu, provide an exposition of a fascinating proof that they got via ChatGPT.)

Are we the only ones that were close to this result? I think not. I think that other people might have had the same idea as us and could have been 1 or 2 Claude-hours away. Or, if they had more time, they could have pushed the idea through more tensors (instead of abandoning the idea on overleaf for years) and would have inevitably tried Coppersmith's paper, and we would have gotten a human proof. But none of us pushed hard enough and a machine did. 

In any case, who gets credit anymore? Is it the machines who assemble all of our joint knowledge and ideas and plow through them with unnerving speed (and $$cost$$)? Is it the people who prompt the machines (i.e., "push the button")? Does a prompt such as "go solve the problem" without any extra hint count? Is it the people who communicate the new knowledge most effectively, and what does that mean? Who gets to publish the new work? Do publications mean more than just exposition? [I am actually pretty reluctant to submit our write-up to STOC, even though I know that most papers will have AI generated results. Our community is so divided about credit and publications that I have started to question the need for STOC as a publication venue, but I digress.]

If you write the paper you might have a good idea about your own contribution, but if you use an LLM even your own intuition can be unreliable because the LLM might supply you hints from other people's research without attribution. For the readers of a paper it is nearly impossible to know where the ideas came from: the authors or a machine (and whose ideas did the machine use?). 

The only thing that a reader can see is whether you brought new understanding. Any remaining credit is in how you communicate. The credit for coming up with the research is now shared across the entire field because the machines exploit all of our ideas at once. And in their thinking, mulling, and regurgitating they even forget where the ideas they used came from.

PS. No LLM was used in writing this.