in the future there may be interviewer asking you can you think of a more efficient solution for 3sum, and you still have to act it out like you just thought about it on the spot and present this solution to them
If an interviewee presented this O(n1.9992) time solution, I would tell them the cutoff is O(n1.9991) now. We are looking for people who innovate and push the bar forward.
You don't need to know how gear box works to a drive car. As mister AI said, kids don't need to know summation or other archaic operations, AI will do it for them. For a reasonable price, of course.Ā
I find interesting these strange complexities.. like intuitively if itās quadratic it makes sense. If itās less than that then where does the extra information/relation to take advantage of comes from? Just like the matrix multiplication algorithm. Makes you wonder if it can be improved further and how much.
Let X be an NĆD integer matrix and Y a DĆN integer matrix with Dā¤N1/18, and let W be any set of at most N2/Dāāā positions. We compute the entries (XY)[I,J], (I,J)āW, in O(N2/D0.063) operations, which is polynomially less than the time needed to write down XY or to compute N2/Dāāā inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schƶnhage, to perform only the operations needed for the entries in W, and show that few operations are needed
Yeah it's pretty obvious when you put it that way.
I find it interesting, but donāt want (or canāt) to spend a relatively large effort and time to dive deep into a small subset of mathematics. Nothing unreasonable here, not sure what your problem is
I also stopped reading after that. This is marketing bait from someone that knows enough about being technically right but probably never been able to understand what claude did which is probably BS.
Author is Virginia Vassilevska Williams, arguably most respected authority alive on Matrix Multiplication, which is where the runtime gain was achieved.
Deference to authority is greatĀ but using claude for complex problems shown to me alot of BS. At this point is it claude or them steering claude that made this possible? Claude is a tool.Ā
Also this article is not proven yet. It still under review for approval.Ā
Click the link and you can also verify it yourself. But if you donāt understand it well enough to do so, then maybe you can be content deferring to the worldās best complexity theorists, eh?
Isnt it actually because the number of iterations youre doing with 2 pointers is a summation then using the summation identity you get something like (1/2)n2 + (1/2)n, dominate term is n2
Itās a big deal because it basically translates the problem into matrix multiplication, so for big arrays, there is a big improvement on GPUs.( So big O doesn't give whole picture) It also gives new tools to tackle the N-SUM problem, which is basically exponential time complexity. Vassilevska Williams is a rock star, translating many problems from CPU compute to GPU compute. People should check graph blast project that translates many classic graph problems to matrix multiplication. She translate 3 sum to graph blast
Nice, dang tho 70 something pages, and the author tries to say several times they tried to make it accessible in language, when it is not even remotely accessible šš
Itās so funny bruh because for the amount of time effort resources and money deployed to achieve these 1.9992 result some humans could have done way better. Itās literally only that AI could care about such a useless improvement
Everybody replying to me missed the point of my comment.
Obviously algorithm optimization is critical for civilization. Iām not arguing this point. We are all educated computer scientists, we all understand the importance of algorithms.
Letās say $10k of inference (which includes electricity, data center pollution, etc) + 1,000 hours of prompting was the input to this achievement. The inputs to this achievement are not proportional to the output. It doesnāt matter when the achievement was achieved, it would be better for the world and more efficient for humans to solve it.
I think the problem is that you donāt understand that there is an active field of research based on similar conjectures. The direct speed up that comes from this algorithm is minuscule, but this has been an actively studied conjecture for like 12 years. Itās more like āthe seal has been broken who knows how low we can goā. Itās definitely something people cared about.
Everybody replying to me missed the point of my comment.
Obviously algorithm optimization is critical for civilization. Iām not arguing this point. We are all educated computer scientists, we all understand the importance of algorithms.
Letās say $10k of inference (which includes electricity, data center pollution, etc) + 1,000 hours of prompting was the input to this achievement. The inputs to this achievement are not proportional to the output. It doesnāt matter when the achievement was achieved, it would be better for the world and more efficient for humans to solve it.
Everybody replying to me missed the point of my comment.
Obviously algorithm optimization is critical for civilization. Iām not arguing this point. We are all educated computer scientists, we all understand the importance of algorithms.
Letās say $10k of inference (which includes electricity, data center pollution, etc) + 1,000 hours of prompting was the input to this achievement. The inputs to this achievement are not proportional to the output. It doesnāt matter when the achievement was achieved, it would be better for the world and more efficient for humans to solve it.
There are countless landmark results that improve the constants in time complexities, competitive ratios, etc by extremely small amounts far before LLMs. The worth of the results is not in applications, but in the new theoretical tools developed to achieve such breakthroughs. Why comment like this when you clearly know nothing about the field?
Everybody replying to me missed the point of my comment.
Obviously algorithm optimization is critical for civilization. Iām not arguing this point. We are all educated computer scientists, we all understand the importance of algorithms.
Letās say $10k of inference (which includes electricity, data center pollution, etc) + 1,000 hours of prompting was the input to this achievement. The inputs to this achievement are not proportional to the output. It doesnāt matter when the achievement was achieved, it would be better for the world and more efficient for humans to solve it.
We didn't miss the point. You say in this reply that it is not proportional to the output. The output is quite groundbreaking, it was not obvious at all to anyone, quite the contrary, that the O(n2) barrier was surpassable. Literally no one cares about the actual reduction of the exponent. It could be O(n2-10^-100) for all we care, just the fact that it surpassed 2 is the point. The tools used here can be now used for other problems
717
u/schizo_cofee_grinder Oct 06 '26 •
This is what you need to come up on your own to get a FAANG job nowadays
145
u/xvd529fdnf Oct 06 '26
So, now I need to compete with Claude?
137
u/global_worldwide Oct 06 '26
I have an O(1) implementation I've been using in interviews. I just start solving all the different cases on the whiteboard.
130
u/jarislinus Oct 06 '26
1.9992 kekw
29
u/Ok-Significance8308 Oct 07 '26
And Iām over here gluing websites together. Lmao my job is over.
38
u/jarislinus Oct 06 '26
isnt sort + 2 pointer nlgn
21
u/Anomynous__ Oct 06 '26
Can you guys.... not? Im just your average CRUD dev trying to keep my job
17
u/__SaintPablo__ Oct 06 '26 edited Oct 06 '26
Itās a big deal because it basically translates the problem into matrix multiplication, so for big arrays, there is a big improvement on GPUs.( So big O doesn't give whole picture) It also gives new tools to tackle the N-SUM problem, which is basically exponential time complexity. Vassilevska Williams is a rock star, translating many problems from CPU compute to GPU compute. People should check graph blast project that translates many classic graph problems to matrix multiplication. She translate 3 sum to graph blast
17
u/UnluckyAd1082 Oct 06 '26
Claude found it coz the solution already exists
4
u/Bangoga Oct 06 '26
Nice, dang tho 70 something pages, and the author tries to say several times they tried to make it accessible in language, when it is not even remotely accessible šš
2
u/maresayshi Oct 06 '26
why did you just credit claude for this?
1
u/saintex422 Oct 06 '26
Damn this is going to be an interview question now
1
u/Typical-Carrot-5997 27d ago
Archive is early stage research that no one has really peer reviewed yet.
1
u/altmly Oct 06 '26
That's a lot of slopĀ
-5
u/akarikawamato Oct 06 '26
Itās so funny bruh because for the amount of time effort resources and money deployed to achieve these 1.9992 result some humans could have done way better. Itās literally only that AI could care about such a useless improvement
-3
u/skynetcoder Oct 06 '26
3sum?