Lower bounds for AC^0 Circuits Augmented with Few Special Gates

One of the most concrete approaches to proving limitations of models of computation is by the theory of Boolean Circuits. A classic result is the exponential size lower bound for constant depth circuits (AC0 circuits). Larger classes of circuits of great interest can be obtained by allowing the circuits to also use more powerful gates, and with these comes the question of proving strong circuit lower bounds. So far the only fully successful result in this setup is the lower bounds of Razborov and Smolensky for circuits augmented with MOD_m gates, for a prime-power m. In this talk we consider finding circuit lower bounds for the following classes of circuits: Let G be a family of Boolean gates (e.g MOD_m gates, MAJORITY gates, threshold gates or symmetric gates), and consider the class of constant depth Boolean AND/OR circuits (AC0 circuits) augmented with only a limited amount of G-gates. Hereby we obtain a problem that can be seen as a "challenge problem" towards approaching lower bounds for the important classes of circuits ACC0 (AC0 circuits augmented with MOD_m gates) and TC0 (AC0 circuits augmented with, say, MAJORITY gates).