https://spectrum.ieee.org/computing/hardware/the-future-of-computing-depends-on-making-it-reversible

]]>https://www.sciencedaily.com/releases/2017/09/170913192957.htm

]]>haha, no, more in the sense how you were once characterizing the P/NP “boundary” as a sort of impenetrable fence – we know it’s separating two domains, but somehow the boundary seems out of reach – we can get closer and closer to it (by making the complexity hierarchy richer and richer), but never touch it (a bit like a fractal).

Quantum Supremacy seems to share some of that a bit. But I guess in that case, the proof will be in the pudding – once QC become a reality, classical algorithm will fall out of favor?

Mea culpa, I hadn’t checked for rebuttals, given the reputation of TLS and thinking that it was too recent anyway. Thanks for the link. It sounds like Gibbs rushed to publish, perhaps nervous about priority. Also quite amazing how the web coordinated reaction came so quickly. ]]>

(Except for the one detail that we need to take g(x mod r) rather than just g(x), this is just taking off-the-shelf results from the crypto literature about building pseudorandom functions in small complexity classes.)

]]>I myself might have thought, “well, if TLS published this, they *must* have fact-checked it, run it by a few experts, etc.,” were it not for my experience with quantum computing! ðŸ™‚