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

The result doesn't actually apply to _all_ algorithms, only oblivious ones. Oblivious algorithms are ones where step i does not depend on decisions made in steps j < i. Almost all useful algorithms are non-oblivious, with some notable exceptions [1]. This work is a step forward towards proving the result for the general case, with little practical usage (and that's perfectly okay).

[1] https://en.wikipedia.org/wiki/Sorting_network



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

Search: