On: New proof dramatically compresses space needed for computation

[JohnKemeny]

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

You need much less memory than time. 126 points, 11 comments, 22 days ago. https://news.ycombinator.com/item?id=44212855

[ALLTaken → JohnKemeny]

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

[utopcell → ALLTaken]

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

[JohnKemeny → ALLTaken]

This is blue skies research and is not expected to have any immediate practical impact whatsoever.