3 ms·
You need much less memory than time
https://arxiv.org/abs/2502.17779 https://arxiv.org/abs/2502.17779
- slicktux 1y agoIt’s nice to see what a little bitwise manipulation can do(XOR)! Low level programming is always fun!
- dang 1y agoRelated. Others? For algorithms, a little memory outweighs a lot of time - https://news.ycombinator.com/item?id=44055347 https://news.ycombinator.com/item?id=44055347 - May 2025 (139 comments)
- laex 1y ago[dupe]
- laex 1y agoSee Kelsey Houston-Edwards's exceptional breakdown of Williams' paper, & Scott Aranson's thoughts on the topic. [1] https://www.youtube.com/watch?v=8JuWdXrCmWg https://www.youtube.com/watch?v=8JuWdXrCmWg [2] https://scottaaronson.blog/?p=8680 https://scottaaronson.blog/?p=8680
- npinsker 1y agoI think the summary at the beginning of your first video is misleading; it's not a way to "trade space for time", at least not in an arbitrary program. The real statement is a bit odder to wrap one's head around -- "every problem solvable in t time on a multitape Turing machine is also solvable in close to √t space". For a Turing machine that already solves a problem in n time and √n space (in other words, a lot of them!), it doesn't say anything.
- LegionMammal978 1y agoWhen you convert a generic Turing machine into a Tree Evaluation instance, you end up with square-root space with respect to the original runtime t, but the new runtime will be far, far slower. IME, with these types of circuit reductions, the runtime typically becomes exponential in the space required, which is just about 'as long as possible'. If we're being pedantic, it's trading time for the space guarantee.
- deleted 1y ago[deleted]
- throwaway81523 1y agoFrom Februray 2025 fwiw. Same result there have been multiple articles here about. I wonder how it would work for Haskell programs (no mutable memory).
- HappMacDonald 1y agoI'd view "no mutable memory" as misleading, because immutable languages can still create a new variable and forget an old one which has the same memory footprint as mutating one variable. Obvious example: the flickering stack frame of tail call elimination.
- curtisf 1y agoHaskell has genuine mutable memory, through State and IO. But even without it, you can emulate mutation in a pure language by threading a "heap" parameter through everything. There's only at most a log factor of extra space and time required in most computing models to "update" a persistent map (though I'm not sure the best way to encode persistent maps directly in Turing machine tapes, which is the model this result is specifically about)
- wewewedxfgdf 1y agoWhat are the practical implications and use cases of this? Is it something like some sort of reverse compiler which creates super efficient code by analyzing the inverse flow of code or something?
- deleted 1y ago[deleted]