Equals DTIME(2polylog(n)).
An especially important subclass of AC, corresponding to constant-depth, unbounded-fanin, polynomial-size circuits with AND, OR, and NOT gates.
Computing the Parity or Majority of n bits is not in AC0 [FSS84].
There are functions in AC0 that are pseudorandom for all statistical tests in AC0 [NW94]. But there are no functions in AC0 that are pseudorandom for all statistical tests in QP (quasipolynomial time) [LMN93].
[LMN93] showed furthermore that functions with AC0 circuits of depth d are learnable in QP, given their outputs on O(2log(n)^O(d)) randomly chosen inputs. On the other hand, this learning algorithm is essentially optimal, unless there is a 2n^o(1) algorithm for factoring [Kha93].
Although there are no good pseudorandom functions in AC0, [IN96] showed that there are pseudorandom generators that stretch n bits to n+Θ(log n), assuming the hardness of a problem based on subset sum.
AC0 contains NC0, and is contained in QACf0 and MAC0.
In descriptive complexity, uniform AC0 can be characterized as the class of problems expressible by first-order predicates with addition and multiplication operators - or indeed, with ordering and multiplication, or ordering and division (see [Lee02]). So it's equivalent to the class FO, and to the alternating logtime hierarchy.
[BLM+98] showed the following problem is complete for depth-k AC0 circuits (with a uniformity condition):
Equals BPTIME(2O((log n)^k)); that is, the class of problems solvable in quasipolynomial-time on a bounded-error machine.
Defined in [CNS99], where the following was also shown:
Equals DTIME(nO(log n)).
Has the same relationship to QP that E does to EXP.
Has the same relation to VPk as QP does to P.
Originated in [Val79b].
The determinant of an n-by-n matrix of indeterminates is VQPk-complete under a type of reduction called qp-projections (see [Bur00] for example). It is an open problem whether the determinant is VPk-complete.