<- Back
Comments (95)
- jdb1729> It would be good to have a formalised proof of the o(n log n) result, for example in Lean. As far as I can tell, one does not yet exist.The result is fully formalized in Lean by @platypii and myself (on Mathlib's TM2 machine), with ongoing improvements to the exponent (currently at 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-leanContributions are welcome!
- kenferry> There is one other aspect of the situation that I would like to emphasise. After two weeks of very hard work, I have managed to understand only a small fraction of [TC26a]. When I ask Fable about the paper, it seems to read and understand the whole thing in just a few minutes, even starting from a fresh context. I know that some readers may be uncomfortable with my anthropomorphic terminology, but I believe that “understand” is accurate, in the sense that the LLM seems to be able to correctly and lucidly answer all kinds of questions about the paper, including about some very fiddly technical details. That is exactly how I would tell that a human colleague has “understood” something. This chasm between human and LLM “speed of thought” is unsettling to say the least.This is very odd, because it just doesn't match my experience with these systems at all. Yes, they do generally SOUND confident, but code (say) that's hard for me to understand is usually hard for the machine to understand as well, and while it is more indefatigable than I am, it's not brighter.This mathematician is in a very good place to evaluate whether Fable gets it or not, but it's weird and counter to my experience.
- Kapura> I have not actually read the paper. In fact, there are three closely related papers [TC26a], [TC26b], [TC26c], and I have not read any of them. I tried, but soon gave up. The math(s) dump does not appear to be strong on exposition. Instead, I asked Fable to explain [TC26a] to me. Fable seems to understand the argument and thinks that it is correct.this does not feel like a healthy place to be
- jdb1729> The new result does not directly imply new complexity bounds for polynomial multiplication over a fixed finite field, say multiplication in F2[x]. The state of the art for this problem is an algorithm that multiplies polynomials of degree n in time O(n log n 4^log*(n)) [HvdH19].@platypii and I obtained a Lean proof of the same improvement for DFT over prime-order finite fields (yielding polynomial multiplication via the convolution theorem): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
- flebronNote in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.
- DannyBeeThe one part that sort of surprises me is he says "The second thing we are missing is that the Model has not in fact found a way of obtaining a program with g < m. (Moreover, Fable tells me this is impossible, but I do not follow the argument yet.)"I'm not sure what argument fable gave him, but this part seems not horribly difficult to prove. I'm sure i'm missing something since i'm not that great at this kind of math.The short reason is that each slice call can at most double the number of nonzero entries, but a transform that would enable g < m must turn a single nonzero entry into (2^m) nonzero entries in a single call.Since the permutes can't generate non-zero entries (since they only move things around), you actually need exactly m slice calls in the initial 2-instruction model given (where you can only do slices and permutes) precisely because of the need to create 2^m non-zero entries where each individual slice op can only double the number (and permutes do nothing)Astra actually comes up with a variant of this argument as well: https://gist.github.com/dberlin/e785c51aff0285c9c0a3ea0f24fa...
- Eji1700I realize this is 100% not the point, but is this an immediately practical breakthrough that will change computing?My extremely limited understanding is “no” as I sorta assume that would be the headline. The main point being that while a MASSIVE improvement over any previous progress it’s still “small” from a practical standpoint.This is not to downplay the very well conveyed problem this might be, but I just want to make sure I even got that right.I do wonder if this will be a major issue for future development or if the math experts in diapers right now will grow up in this world and have tools and understanding to assist and we’re just in a rough transition, but unfortunately that’s about as much as I can contribute.
- yaoke259Awesome write up and intro by a fellow Sydney-sider, kept me hooked! As someone who's not a maths wizard, the technical details flew by my head but the prose allowing me to empathise deeply with those in the field was very enlightening. I never realised how big of a deal the maths dump was and how much it has shaken up the field. I guess we are all just trying to figure out this whole "intelligence on tap" thing together.
- jonhohle> I assume that by now the Company’s employees are aware of the pain and profound sense of loss that this event has caused in my professional community.I’m trying to come to terms with this myself. I agree that this future is inevitable, and progress will come regardless.I feel a lot like Grant in Jurassic Park right now.
- kleiba2Interesting that AI apparently doesn't write papers for humans: even experts struggle to understand them. But other AIs do. So AI basically writes papers for other AIs.
- ajkjkI really enjoy the writing style here.edit: I mean this seriously. This kind of thing> Some of my colleagues believe that this is a nefarious Company, whose only goal is profit, if necessary at our community’s expense. Perhaps there is some truth to this, but I think it is missing the larger point. The fact is that there now exists an automated system that can perform mathematical research — at least the part that involves “solving hard problems” — far better than any human. Now that such a system has been demonstrated, it is clear that results like these were bound to start appearing soon anyway. I do not blame the Company for getting there first. Who got there first is an irrelevant detail, a historical footnote.is very pleasantly honest and well-thought-out.
- SuracQuestion is: do i still use the integer mull command of my cpu or should i write it myself in c. I think the hardware still wins. But will it have a impact on future cpu ALU designs?
- WindyTreeI always wondered about breaking down the O( n log n) FFT convolution multiplier into truly discrete pieces to see if you can shrink it more, last I checked languages like Python that use big integers still weren’t using it, and when I implemented it it used complex floats. I don’t see why it couldn’t be THE multiplier, plus it works in constant time with optics.
- MiroslavPokorny> Executive summary (longer version) > The bottom line is that I think the claimed result is plausible. I have not actually read the paper.
- joe_the_userTo understand the new integer multiplication algorithm, one must first understand essentially everything in the 2021 algorithm. It is impossible for me to explain all of this here ... Readers interested in the details should consult [HvdH21 - his paper], which by all accounts is a superbly written paper.That made me chuckle...
- cachiusNice domain, UNSW!web.maths.unsw.edu.au fills the whole address bar on mobile