[kaffekaka]

Phrased like that it sounds like a qualitative difference between "low" and "high" dimensional spaces. But isn't it simply a consequence of the fact that the more dimensions you have, the less likely that randomly distributed, sparse non-zeros will end up in the same positions?

I.e. simply a quantitive difference.

[klodolph]

Any extreme quantitative difference is going to be a qualitative difference.