alt Hacker NewsI am trying to understand how the paper OP posted can be translated into anything that improves current algorithms.
Can actually any current algorithms improved by this?? Or is that only the case if the hardware itself is improved?
I am baffled
Replies
JohnKemeny • yesterday at 9:25 PM
This is blue skies research and is not expected to have any immediate practical impact whatsoever.
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