Qingyu's blog

Today's News: O(n^{2-eps}) algorithm for 3SUMs and APSP is found by Claude
By Qingyu, 3 weeks ago, In English

I guess people on CF might be interested to read Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs on ArXiv. The authors stated that an Anthropic model discovered an algorithm that refutes the 3SUM and APSP hypotheses. Let's rock and roll.

  • Vote: I like it
  • +324
  • Vote: I do not like it

»
3 weeks ago, hide # |
 
Vote: I like it +54 Vote: I do not like it

inb4 $$$\omega = 2$$$ for matmul next year

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it -63 Vote: I do not like it

I don't know who would be interested in reading 60 pages of slop

Maybe provide a summary of how it was proven and why it's important?

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it +124 Vote: I do not like it

    this is not slop. this paper is written by experts in the field based on the proof provided by claude.

    → Reply
    • »
      »
      »
      3 weeks ago, hide # ^ |
       
      Vote: I like it -26 Vote: I do not like it

      Anthropic is genuinely respectful.

      → Reply
    • »
      »
      »
      3 weeks ago, hide # ^ |
       
      Vote: I like it -17 Vote: I do not like it

      if you don't care additional results in sections 4 and 5(results till section 3 is enough for bettet 3SUM and APSP) it is not that difficult

      → Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it +75 Vote: I do not like it

    TLDR: In the past decades, fine-grained complexity theorists developed a web of reductions, and it turns out that if certain kinds of matrix multiplication problems have faster-than-known algorithms, then this would refute APSP and 3SUM.

    Consider the problem of multiplying an $$$N\times N^{0.1}$$$ and $$$N^{0.1} \times N$$$ matrix. An old paper by Coppersmith showed that it can actually be done in $$$O(N^2 \log^2 N)$$$ time, and he offered two algorithms.

    Note that the output has $$$N^2$$$ numbers. What if we don't want the whole output, but only care about a sparse set of entries, say $$$N^{1.99}$$$ many entries?

    The new paper tries the following thing: Pick one of Coppersmith's algorithms, first write it down as an arithmetic circuit, delete the output entries we don't want, and then recursively prune the unused gates. Surprisingly, due to some well-behaved combinatorial structure of the program, the circuit dramatically simplifies to about $$$N^{1.99999}$$$ time. Then the dominoes fall.

    It is not a technically involved paper, but is very surprising since no one believed that it would work.

    → Reply
    • »
      »
      »
      3 weeks ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I see that the abstract refers to an All-Edges Sparse Triangle problem, which can be reduced from APSP and 3SUM, but is there "fast" intuition you can provide for why we would only care about a sparse set of entries?

      → Reply
      • »
        »
        »
        »
        3 weeks ago, hide # ^ |
         
        Vote: I like it +9 Vote: I do not like it

        That's subtle. There is a problem called exact triangle: Find a triangle in a weighted graph whose total weight is a given target. It is already known that this problem is both APSP- and 3SUM-hard. You can imagine there might be some ways to tackle this problem by hashing the weights, which might give you a sparse graph.

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Thanks for the follow-up! My immediate naive thought about hashing the weights would be that it essentially goes back to the "standard" approach for 3SUM, but I suppose I should just read the full paper.

          → Reply
    • »
      »
      »
      28 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Thanks for the writeup! Its always a pleasure to read your comments

      → Reply
    • »
      »
      »
      38 minutes ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Perhaps even ETH might be false: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf

      Seems like a tough year to be working in fine-grained complexity (at least, outside of your academic branch) but at least there might be a new OpenAI-sponsored conference for this area, according to https://x.com/rrwilliams/status/2114833324107759983

      → Reply
»
3 weeks ago, hide # |
 
Vote: I like it -31 Vote: I do not like it

Still waiting for $$$P \neq NP$$$ proof(or $$$P = NP$$$)

→ Reply
»
3 weeks ago, hide # |
← Rev. 5  
Vote: I like it +24 Vote: I do not like it

This is very interesting! Seems AI lean proofs is the future of mathematics. Lets just hope that AI can learn to also write readable proofs instead of slop. Maybe they need more training on codegolfing to write shorter proofs xd.

On the topic of universal quantifiers vs. existential quantifiers. It is interesting to note that both this and the Navier-Stokes results are of the existential kind. They only needed to find one counterexample/algorithm for their proofs. I wonder how long it will take until AI proves an important "for all" claim. I would expect that type of claim to be a lot more difficult to prove.

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

when I verified theorem 5 I thought it was a standard theorem I didn't realize that it can be used to improve bounds for 3SUM and APSP until I verified the proof of theorem 19(it uses hash to separate weights a bit (n^C , independent of v) then uses theorem 19 to use the gap)

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Waitting

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it -20 Vote: I do not like it

I slumped in my chair, as if witnessing a nuclear explosion before my eyes

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it +50 Vote: I do not like it

https://qoj.ac/problem/14018

this came 3176 years sooner than i expected

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

yesterday's news now (and very boring too). $$$AI$$$ has recently solved the entire math.

→ Reply
»
29 hours ago, hide # |
 
Vote: I like it -17 Vote: I do not like it

this is not slop. this paper is written by experts in the field based on the proof provided by claude and gpt

→ Reply