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

even though the constant is tiny, this breaks the long held assumption that nlogn is the minimal possible bound, so further research seemed unfruitful. this discovery will now trigger more research in this area, and probably more optimal algorithms will be discovered.

Like matrix multiplication, the common assumption was that it cannot be improved past n^3. Then Strassen broke the barrier (with a more significant constant) which caused intensive research - and now we are around n^2.3..2.4.

 help



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: