> 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].
Note 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.
Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
> 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.
Why not? If mathematicians in the field cannot understand the papers, but tools at our disposal can, why not use them? What is "unhealthy" about that? Just seems like it's the reality of the world now.
Awesome 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.
You don’t need to be a math wizard. Just upload the paper to an AI and ask, “Explain this like I’m five.” Then, with each follow-up prompt, increase the age and level of expertise you want it to assume.
@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...
f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
s/must shrink/must eventually shrink, after finitely many n/
Equivalently, must go to zero in the limit.
O(2n+1) = O(2n) = O(n)
o(2n+1) > o(2n) > o(n)
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
Big O is sort of like <=. little o is sort of like <.
https://dl.acm.org/doi/10.1145/1008328.1008329
O(n) is: "there exists a K such that, for sufficiently large n, K*n is always larger".
o(n) is: "for every K, for sufficiently large n, K*n is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.)
This isn't quite correct. O(g) doesn't require the limit to exist.
If you were joking then maybe you got me
https://stackoverflow.com/questions/1364444/difference-betwe...
this does not feel like a healthy place to be