2 ms·
Related: For algorithms, a little memory outweighs a lot of time. 343 points, 139 comments, 39 days ago. https://news.ycombinator.com/item?id=44055347 https://
by JohnKemeny 1y ago
Related:
For algorithms, a little memory outweighs a lot of time.
343 points, 139 comments, 39 days ago.
https://news.ycombinator.com/item?id=44055347 https://news.ycombinator.com/item?id=44055347
You need much less memory than time.
126 points, 11 comments, 22 days ago.
https://news.ycombinator.com/item?id=44212855 https://news.ycombinator.com/item?id=44212855
- ALLTaken 1y agoI 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 agoThis is blue skies research and is not expected to have any immediate practical impact whatsoever.
- utopcell 1y agoThe 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