And that shouldn't be surprising. Look at brilliant physicists. Most end up in either the theoretical or experimental side, and are often quite bad at the other. Likewise, theorem heavy CS has its place, but getting through a program like that doesn't mean that you can write a for loop (I've interviewed Stanford grads that fumbled and failed though that), design readable, robust software, push through a sea of decisions and make effective, near optimal decisions (the whole SW life cycle is a n-dimensional optimization problem), get along with peers, and so on.
There is a huge cachet attached to degrees from certain institutions that really isn't deserved, in my opinion. In that sense the paper is "pretty". It's not a slam of the effort anyone at is undoubtedly making at the school, but the reverent regard with which it is regarded.