Ryan Williams strikes again

Because of a recent breakthrough by Cook and Mertz on Tree Evaluation, Ryan now shows that every problem solvable in t time on a multitape Turing machine is also solvable in close to √t space
As a consequence, he shows that there are problems solvable in O(n) space that require nearly quadratic time on multitape Turing machines
If this could be applied recursively to boost the polynomial degree, then P≠PSPACE
On Facebook, someone summarized this result as “there exists an elephant that can’t fit through a mouse hole.” I pointed out that for decades, we only knew how to show there was a blue whale that didn’t fit through the mouse hole
I’ll be off the Internet for much of today (hopefully only today?) because of jury duty! Good thing you’ll have Ryan’s amazing new paper to keep y’all busy…