A quick glance seems to indicate that they are achieving these linear time algorithms through massive parallelization. This is "cheating" because to do a linear-time sort of size n, you need O(n) processing units. While they seem to be arguing that this is acceptable because processing is becoming more and more parallel, this breaks down for large n. One can easily use traditional algorithms to sort a billion elements in O(n * log n); however for their algorithm to sort such a list in O(n) time, they need a billion (times some constant factor) times more processing units than to sort a list of size n.

I'm also vaguely perplexed by their basic argument. They want to have programming tools and computational models which are closer to the metal to take advantage of the features of new machines. This ignores the fact that the current abstractions exist, not just for historical reasons, but because they are easy to reason about.

This is all from a fairly cursory read of their paper, however, so take it with a grain of salt.