Felipe Cucker and Michael Shub. Generalized Knapsack problems and fixed degree separation. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, and Roman Smolensky. A lower bound for randomized algebraic decision trees. Friedhelm Meyer auf der Heide.
Lower time bounds for solving linear diophantine equations on several parallel computational models.
On the parallel complexity of Gaussian elimination with pivoting.