Terminology
- $CC^0[m]$ is the set of polynomial-sized, constant depth circuits consisting entirely of $MOD_m$ gates for some $m \geq 2$, where a $MOD_m$ gate outputs a 1 if and only if the sum of its inputs is a multiple of $m$. Here, I am interested in limiting the depth to 2 (so a layer of gates, followed by an output gate), but allowing the size to be exponential (or really any arbitrary size).
- A generalized $MOD_m$ gate $MOD_m^A$ is also characterized by some output set $A \subseteq \{0,1,2,...,m-1\}$ where the output of the gate is 1 if and only if the sum of the inputs to the gate mod $m$ is in $A$.
- Finally, instead of inputs to the circuit being binary, we allow inputs to take on the values $\{0,1,2,...,m-1\}$.
Motivation
It is a well-known fact of Barrington et al. that depth-2 exponential-sized $CC^0[m]$ circuits can compute arbitrary decision problems over binary inputs as long as $m$ is composite with at least two distinct prime factors (e.g. $m=6$). It is easy to show that, if we can compute arbitrary decisions over $n$ binary inputs in depth $d$, we can also compute arbitrary decisions over $\frac n6$ inputs from $Z/mZ$ in depth $d+1$, so we have that depth-3 exponential-sized $CC^0[m]$ circuits can compute arbitrary decision problems over $Z/mZ$. However, this still leaves open the case of depth-2 exponential-sized $CC^0[m]$ circuits with inputs from $Z/mZ$.
Question
Assuming $m$ is composite with at least 2 distinct prime factors, does there exist some decision problem over the alphabet $Z/mZ$ that cannot be computed by exponential-sized depth-2 $CC^0[m]$ circuits with generalized gates?