It's fun to think about, but the presentation played fast and loose with a few concepts. Sparked some lively discussion because of that. I really like the idea of needing to count random memory accesses as costing more than sequential accesses when analyzing algorithms in a big-O-type notation.
So people developed algorithms that maximised locality of reference, like B-trees. An interesting line of work in this vein is that of cache-oblivious algorithms :)
Maybe I'm missing something, but why's that?
To the rest of your comment: all good points.
(This ultimately violates the Bekenstein bound - as your server cube grows it will eventually collapse into a black hole - but this is not really a concern with forseeable technology! More practically, though, Earth's gravity makes it hard to build very high in the air, which limits you to O(N^1/2), and things like cooling and maintenance access probably impose a limit somewhere in between.)
The truth is that complexity theory is always done relative to some abstract machine model, and as with all models it's up to you to determine if the model is a good fit for your practical reality. "To the extent that mathematics reflects reality it is not certain, and to the extent that it is certain it does not reflect reality." There exist abstract models, like the cache oblivious model, that do a somewhat better job of grappling with this issue but don't require to just throw up your hands and rely solely on benchmarks of real hardware. There is probably room for new theory in this area.
[1] not throughput, which isn't as hard to scale up