3 ms·

I am trying to understand how the paper OP posted can be translated into anything that improves current algorithms. Can actually any current algorithms improve

I 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

JohnKemeny 1y ago
This is blue skies research and is not expected to have any immediate practical impact whatsoever.
utopcell 1y ago
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 https://en.wikipedia.org/wiki/Sorting_network