Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes.Furst Saxe Sipser to Yao to Hastad are all parity and random restrictions. Razborov/Smolensky is approximate polynomial with parity (ok, mod gates). Aspnes et al use weak degree on parity. Further, Allender Hertrampf and Beigel Tarui are about using Toda for small classes. And Razborov/Beame with decision trees.  All of these fall into the parity basket. 1) What are other natural problems (apart from parity) that can be shown directly not to be in $AC^0$? 2) Anyone know of a drastically different approach to lower bound on AC^0 that has been tried?
Parity and $AC^0$
cc.complexity theory;complexity classes;lower bounds;circuit complexity