Which results in complexity theory make essential use of uniformity? A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like time and space hierarchy theorems) make essential use of uniformity as they need to simulate the programs in the smaller class. 


  Which results in complexity theory (other than diagonalization proofs) use uniformity essentially?
I have asked many experts essentially this question, and the answer I always get is: none.  Diagonalization proofs obviously use uniformity, and these are at the heart of the time and space hierarchy theorems, as well as Fortnow-Williams type of time-space lower bounds.  As far as I know, all the other lower bounds we know of, both for complexity class separations and for data structures, seem to be non-uniform.  It would be great to hear that I'm wrong though :).