The 4k demo guys' main compression was in size. I'm not sure if that's what you were implying - but the 4k demo is very cpu heavy and would not run on any older consoles - I had trouble running one of those demos a few years back. There's always some sort of minimum tradeoff with any sort of optimization.
Its about getting as much fun as possible into the available space. Same as with an old console (or a new one...)
Yes, my point was that these techniques could not be done on old hardware, meaning it's possible to make even more "compact" (as in resources/size-ratio and functionality/size-ratio) programs today.
You could fit 64 of those 4k demos into a NES cartridge.
I'm personally totally blown away by what these guys do with 4096 bytes... when you start thinking about how little code this really is, it's pretty amazing to see a 5 min flyby in a fully textured and lighted 3d environment, including nice music!
4096 bytes is the size of one (1!) 32x32 sprite in rgba color.