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

From the abstract:

>In this work, we prove that if a central conjecture in the area of network coding is true, then any constant degree boolean circuit for multiplication must have size Ω(nlgn), thus almost completely settling the complexity of multiplication circuits

So, given an unproven assumption and also given that we are constrained to doing multiplication on a boolean circuit, this may be "perfect" in a sense.

Seems like the title is mostly just clickbait.



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

Search: