Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

(integer multiplication, not matrix multiplication, right?)
 help



I thought the nlogn^.9999 was for fft

It was for both fft and integer multiplication (different bounds but both slightly under nlogn)

It was both actually.

No. They have a new upper bound for matrix multiplication, but it's O(n^2.25). You can't do less than n^2 for obvious reasons (size of the input and output).



Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: