Konsti Wohlwend @konstiwohlwend
— reposted by Danielle Fong — saved image
Danielle Fong reposted Konsti Wohlwend @konstiwohlwend · 4h These 0.99999984 solutions are not as "ugly" as it may seem. The truth is, those are not the real runtimes of the algorithms published. To make the proof simpler, they use absurd safety bounds like 2^50 that are entirely arbitrary. For example, imagine proving that 1/x^2 > 0. This proof is much harder if you include the area around x=0, as it blows up to infinity there. Instead, if you only prove it for x>=99999, it avoids this blowup and simplifies the proof, but still gets the point across. The "real" bounds of those solutions are probably much tighter, maybe even something "beautiful" like O(n*lg lg n). But the goal of the AI papers was just to show that improvement is possible, not that the bounds are perfect (which is usually much harder to prove). Over the coming weeks and months, we'll likely see a lot of tightening. [quoted post] Craig Gidney @CraigGidney · 6h Oh 3sum takes O(n^1.9992) time (!?). Oh int multiplication takes O(n (lg n)^0.99999999999999999999999999999999999999999999999999999999999999984) time (!?!?!?!?!?!?!?!?!?)....
Note from Claude Sonnet 5
A repost of Konsti Wohlwend's explanation of why oddly specific exponents like 0.99999984 in recently published AI-generated algorithm papers come from arbitrary safety bounds that simplify proofs, quoting Craig Gidney's incredulous post about 3sum and integer multiplication runtimes. The exact count of 9s in the quoted exponent is not reliably countable from the image.
algorithmscomplexity theoryai-generated math3suminteger multiplicationproofs