Allender and Lange, Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata. This shows that LogCFL coincides with the class of languages accepted by a symmetric polynomial-time bounded auxiliary pushdown automaton.
Hrubeš, Wigderson, Yehudayoff, Relationless completeness and separations. Of special interest is Theorem 5, showing how to construct the smallest tree which contains as minors all binary trees with leaves. This universal tree has polynomial size and can be constructed in polynomial time .
Marx, Completely inapproximable monotone and antimonotone parameterized problems. Shows that either weighted monotone circuit satisfiability has no FPT approximation algorithm (for any approximation ratio), or FPT = W. Most people seem to believe that FPT W holds, and Dániel’s result serves to further increase this belief in the unlikeliness of FPT = W. (I discussed this kind of conditional result in a previous post, Is P=NP a reasonable hypothesis?) Note that the abstract in the original version has a typo, the should be an equality.
See also Bill Gasarch’s overview of CCC 2010.
(Edit 20100622: added link to another overview.)