Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?

Question

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?

Answer 1

This is not a complete answer; just partial progress.

For certain output sets of the output gate (the only gate on the second layer), we can prove that there are functions uncomputable by this type of circuit. Let $m = p_1^{k_1} p_2^{k_2} ... p_r^{k_r}$ for some primes $p_i$ and powers $k_i \geq 1$; then:

• For any prime $p_i$ and power $1 \leq k \leq k_i$, let the output set $A$ of the final gate consist exactly of multiples of $p_i^k$, i.e. $A = \left\{0, p_i^k, 2p_i^k, 3p_i^k, ..., m-p_i^k\right\}$. Then the output gate functions as a $MOD_{p_i^k}$ gate. Then, let the inputs to the circuit be from the set $\left\{0, \frac m{p_i^k}\right\}$; then the bottom layer of gates will act identically to $MOD_{p_i^k}$ gates over a binary input. Therefore, the circuit will act as a $MOD_{p_i^k} \circ MOD_{p_i^k}$ circuit over a binary input, which is known to be unable to compute the $OR_n$ function, even given unlimited size.
• Let the output set $A$ of the final gate be any singleton, and assume we have a circuit for $OR$ over $Z/mZ$. We can "absorb" constant wires into the circuit by offsetting output sets by a constant amount, without changing the functionality of the circuit. Similarly, for any gate on the first layer that is "on" when the input is $\vec 0$, we can invert the output set of that gate, invert the wire weight of that gate to the output gate, and offset the final output set, all without changing the functionality of the circuit. This leaves us with a $MOD_m \circ MOD_m$ circuit with no constant wires, all first-layer gates off with an input of $\vec 0$, and a singleton output set on the final gate. Next, by the Chinese Remainder Theorem, a $MOD_m$ gate with a singleton output set is the same as $AND\left(MOD_{p_1^{k_1}},MOD_{p_2^{k_2}},...,MOD_{p_r^{k_r}}\right)$, where each of the $MOD_{p_i^{k_i}}$ gates is offset by some constant wires. Now, for each $p_i^{k_i}$, we restrict the input to be from $\{0,m/(p_i^{k_i})\}$, so that the bottom layer of gates functions as $MOD_{p_i^{k_i}}$ gates. We therefore have that our circuit is identical to an $AND\left(MOD_{p_1^{k_1}} \circ MOD_{p_i^{k_i}}, MOD_{p_2^{k_2}} \circ MOD_{p_i^{k_i}}, ..., MOD_{p_r^{k_r}} \circ MOD_{p_i^{k_i}}\right)$. The only way this is possible is if at least one of these circuits computes $OR$, and the rest either compute $OR$ or a constant 1. Specifically, one of these circuits must be $MOD_{p_i^{k_i}} \circ MOD_{p_i^{k_i}}$, and since this circuit cannot compute $OR$, it must compute a constant 1. However, since there are no constant wires in the lower layer, this must mean that the second layer $MOD_{p_i^{k_i}}$ gate contains 0 in its output set. We can repeat this process for each $p_i^{k_i}$ to show that each $MOD_{p_i^{k_i}}$ gate in the second layer must have 0 in its output set. However, going back to our original circuit, this implies that our $MOD_m$ output gate has 0 in its output set (since it is just the $AND$ of the various $MOD_{p_i^{k_i}}$ gates). This means on an input of $\vec 0$, the first layer will not have any gates that are on, and the final gate will therefore output a 1 and not compute $OR$, a contradiction. Therefore, the final output set cannot be a singleton.

This still leaves the possibility of a final output set of the form e.g. $\{p_1,p_2\}$ providing arbitrary computation.