Funny you mention probabilistic algorithms. If I’m not mistaken one of the OpenAI results is that most of the probabilistic methods (specifically those that use a logarithmic amount of space)-4 have non-probabilistic versions that are as efficient in time and space (L = RL = BPL)
replyFor linear programing, the interior point method has a polynomial worst case.
replyIt also not probabilistic, so linear programing is not rely a good example
Incidentally, Ryan Williams says (https://x.com/rrwilliams/status/2114891838377320784):
reply> In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result. Apparently they are safe...
so if you trust his trust of OpenAI, then this has no (immediately obvious) bearing on cryptosystems for now.
Not by this result. But it opens up a new area of problems to hammer on that might get somewhere.
replySeeing the panicked state of the PHP ecosystem at the moment, and having worked in the financial system in the past, I dread the thought of what would happen to global banking if a frontier model broke a maths problem that underpins our crypto systems...
replydeleted
reply