logoalt Hacker News

adgjlsfhk1 • today at 6:11 AM • 1 reply • view on HN

this blog post is notably wrong on several counts. Firstly, the <nlogn multiplication is using a traditional multi tape Turing machine model which doesn't have the same tricks the dft result uses (and the dft result can similarly be reformulated at the expense of a less readable paper.

Also the 10^-13 isn't an optimized number. Current results are up about 10 orders of magnitude (10^-3) and show little sign of stopping. it's seems entirely plausible that we might get to nsqrt(log(n)) (with a likely still astronomical constant)


Replies

throwaway198846 • today at 8:46 AM

Is that a natural barrier for the current method or we could also have n(log n)^epsilon ?