Same as AC0, except now we're allowed a single unbounded-fanin majority gate at the root.
Defined in [JKS02].
MAC0 is strictly contained in TC0 [ABF+94].
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):
βkMAC0 is the class of decision problems solvable by a uniform family of polynomial-sized MAC0 circuits that accept O(logk n) nondeterministic input bits, with the same acceptance mechanism as MAC0.
βMAC0 is the union of βkMAC0 over all constant k.
For any constant k, βkMAC0 is contained in βkTC0. In particular, β1MAC0 is contained in β1TC0 = TC0.
We note that βkMAC0 = NMAC0(logk n).
The notion of a non-deterministic NC circuit was introduced in [Wol94]; see NNC(f(n)).