My gut feeling is there is no "tractable" line. All subsets of problems are tractable.
Via analogy, think of auto-encoders or dimensional reduction. You may have 500^2 dimensions representing each pixel in an image recognition task. Representing all of that data in a lower dimensional space is impossible via pigeonhole. But if you only feed your net the subset of images of cats (or dogs, or only images commonly taken on cameras) it's actually a much smaller space and it can be represented efficiently in lower dimensions. And you can take any subset and it will have structure and because it has structure it can be represented more efficiently and solved efficiently. The fact that we're only interested in a subset of the problem space it what makes it efficient for us to solve.
Even if we generated "random" pixels, but used a method to only generate a subset of that noise (ie gave it structure), then we'd be able to reduce dimensions on it.
There is no line of portion of the space that's tractable or not, it's the fact we're working with a structured portion of the space that always makes it tractable.
I think it will be phenomenal when it's finally common place, but I think the comment they're making is "It's amazing that there's this think called compression and it works on, and works well on just about anything we want to compress. I understand theoretically it should make some things larger, but just about everything I try to compress it makes smaller!" Of course, it does because the only things we want to compress are things that have enough inherent structure that we want to save and share them. If all we were interested in were just the output of a random number generator (which wouldn't compress), then we'd never want to compress it anyway.
It's phenomenal actually. The only problems it works on are the problems we want to solve. Because the problems we want to solve have structure in them, they follow some rules (which is why we care about them to begin with).