Same as AC0, but now "MOD m" gates (for a specific m) are allowed in addition to AND, OR, and NOT gates. (A MOD m gate outputs 0 if the sum of its inputs is congruent to 0 modulo m, and 1 otherwise.)
If m is a power of a prime p, then for any prime q not equal to p, deciding whether the sum of n bits is congruent to 0 modulo q is not in AC0[m] [Raz87] [Smo87]. It follows that, for any such m, AC0[m] is strictly contained in NC1.
However, if m is a product of distinct primes (e.g. 6), then it is not even known whether AC0[m] = NP!
See also: QAC0[m].
Same as AC0[m], but now the constant-depth circuit can contain MOD m gates for any m.
Contained in TC0.
Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [Yao90].
According to [All96], there is no good evidence for the existence of cryptographically secure functions in ACC0.
There is no non-uniform ACC0 circuits of polynomial size for NTIMES[2n] and no ACC0 circuit of size 2nO(1) for ENP (The class E with an NP oracle). These are the only two known nontrivial lower bounds against ACC0 and were recently discovered by [Wil11].
The set of problems solvable by by constant-depth circuits having only MODm gates for constant .
It was shown in [CW22] that any symmetric function can be computed by depth-3 CC0 circuits with size 2O(na) for any constant a. Such a circuit uses a modulus m with size at most (1/a)2/a.
This is in contrast with AC0 which requires size 2O(n1/(d-1)) for depth d circuits computing arbitrary symmetric functions [Has87]. Even AC0[m] for prime power m requires size 2O(n1/(2d)) for depth d [Raz87] [Smo87].
Same as QAC0, except that now Mod-m gates are also allowed. A Mod-m gate computes whether the sum of a given set of bits is congruent to 0 modulo m, and exclusive-OR's the answer into another bit.
Defined in [Moo99].
