One of the major ambitions of complexity theory is to prove lower bounds for explicit 
problems against non-uniform circuits. On the other hand, hierarchy theorems and their 
variants are well known to give lower bounds against circuits satisfying strong 
(DLOGTIME) uniformity conditions. There are two natural ways to interpolate between 
strong uniformity and non-uniformity: (1) Allow a weaker notion of uniformity such as P-
uniformity (2) Allow the strong uniform circuits to take a small amount of advice. I will 
discuss recent results showing new lower bounds in these settings, and some 
consequences of these results. The results include a hierarchy theorem for non-
deterministic polynomial time where the lower bound is against n^{o(1)} bits of advice, 
and, for any fixed k, a lower bound in P against P-uniform Boolean circuits of size n^k. 
The proof technique for the latter result involves a connection between the paradigms 
(1) and (2) of interpolative uniformity.

Based on joint works with Lance Fortnow and Ryan Williams.