<p><strong>This is not a complete answer</strong>; just partial progress.</p>
<p>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 <span class="math-container">$m = p_1^{k_1} p_2^{k_2} ... p_r^{k_r}$</span> for some primes <span class="math-container">$p_i$</span> and powers <span class="math-container">$k_i \geq 1$</span>; then:</p>
<ul>
<li>For any prime <span class="math-container">$p_i$</span> and power <span class="math-container">$1 \leq k \leq k_i$</span>, let the output set <span class="math-container">$A$</span> of the final gate consist exactly of multiples of <span class="math-container">$p_i^k$</span>, i.e. <span class="math-container">$A = \left\{0, p_i^k, 2p_i^k, 3p_i^k, ..., m-p_i^k\right\}$</span>. Then the output gate functions as a <span class="math-container">$MOD_{p_i^k}$</span> gate. Then, let the inputs to the circuit be from the set <span class="math-container">$\left\{0, \frac m{p_i^k}\right\}$</span>; then the bottom layer of gates will act identically to <span class="math-container">$MOD_{p_i^k}$</span> gates over a binary input. Therefore, the circuit will act as a <span class="math-container">$MOD_{p_i^k} \circ MOD_{p_i^k}$</span> circuit over a binary input, which is known to be unable to compute the <span class="math-container">$OR_n$</span> function, even given unlimited size.</li>
<li>Let the output set <span class="math-container">$A$</span> of the final gate be any singleton, and assume we have a circuit for <span class="math-container">$OR$</span> over <span class="math-container">$Z/mZ$</span>. We can &quot;absorb&quot; 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 &quot;on&quot; when the input is <span class="math-container">$\vec 0$</span>, 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 <span class="math-container">$MOD_m \circ MOD_m$</span> circuit with no constant wires, all first-layer gates off with an input of <span class="math-container">$\vec 0$</span>, and a singleton output set on the final gate. Next, by the Chinese Remainder Theorem, a <span class="math-container">$MOD_m$</span> gate with a singleton output set is the same as <span class="math-container">$AND\left(MOD_{p_1^{k_1}},MOD_{p_2^{k_2}},...,MOD_{p_r^{k_r}}\right)$</span>, where each of the <span class="math-container">$MOD_{p_i^{k_i}}$</span> gates is offset by some constant wires. Now, for each <span class="math-container">$p_i^{k_i}$</span>, we restrict the input to be from <span class="math-container">$\{0,m/(p_i^{k_i})\}$</span>, so that the bottom layer of gates functions as <span class="math-container">$MOD_{p_i^{k_i}}$</span> gates. We therefore have that our circuit is identical to an <span class="math-container">$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)$</span>. The only way this is possible is if at least one of these circuits computes <span class="math-container">$OR$</span>, and the rest either compute <span class="math-container">$OR$</span> or a constant 1. Specifically, one of these circuits must be <span class="math-container">$MOD_{p_i^{k_i}} \circ MOD_{p_i^{k_i}}$</span>, and since this circuit cannot compute <span class="math-container">$OR$</span>, it must compute a constant 1. However, since there are no constant wires in the lower layer, this must mean that the second layer <span class="math-container">$MOD_{p_i^{k_i}}$</span> gate contains 0 in its output set. We can repeat this process for each <span class="math-container">$p_i^{k_i}$</span> to show that each <span class="math-container">$MOD_{p_i^{k_i}}$</span> gate in the second layer must have 0 in its output set. However, going back to our original circuit, this implies that our <span class="math-container">$MOD_m$</span> output gate has 0 in its output set (since it is just the <span class="math-container">$AND$</span> of the various <span class="math-container">$MOD_{p_i^{k_i}}$</span> gates). This means on an input of <span class="math-container">$\vec 0$</span>, the first layer will not have any gates that are on, and the final gate will therefore output a 1 and not compute <span class="math-container">$OR$</span>, a contradiction. Therefore, the final output set cannot be a singleton.</li>
</ul>
<p>This still leaves the possibility of a final output set of the form e.g. <span class="math-container">$\{p_1,p_2\}$</span> providing arbitrary computation.</p>

CC BY-SA 4.0
2021-11-17T18:53:47.247Z
2021-12-07T23:41:27.530Z
2021-12-07T23:41:27.530Z
Jake
<h3>Terminology</h3>
<ul>
<li><span class="math-container">$CC^0[m]$</span> is the set of polynomial-sized, constant depth circuits consisting entirely of <span class="math-container">$MOD_m$</span> gates for some <span class="math-container">$m \geq 2$</span>, where a <span class="math-container">$MOD_m$</span> gate outputs a 1 if and only if the sum of its inputs is a multiple of <span class="math-container">$m$</span>. 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).</li>
<li>A generalized <span class="math-container">$MOD_m$</span> gate <span class="math-container">$MOD_m^A$</span> is also characterized by some <em>output set</em> <span class="math-container">$A \subseteq \{0,1,2,...,m-1\}$</span> where the output of the gate is 1 if and only if the sum of the inputs to the gate mod <span class="math-container">$m$</span> is in <span class="math-container">$A$</span>.</li>
<li>Finally, instead of inputs to the circuit being binary, we allow inputs to take on the values <span class="math-container">$\{0,1,2,...,m-1\}$</span>.</li>
</ul>
<h3>Motivation</h3>
<p>It is a well-known fact of Barrington et al. that depth-2 exponential-sized <span class="math-container">$CC^0[m]$</span> circuits can compute arbitrary decision problems over binary inputs as long as <span class="math-container">$m$</span> is composite with at least two distinct prime factors (e.g. <span class="math-container">$m=6$</span>). It is easy to show that, if we can compute arbitrary decisions over <span class="math-container">$n$</span> binary inputs in depth <span class="math-container">$d$</span>, we can also compute arbitrary decisions over <span class="math-container">$\frac n6$</span> inputs from <span class="math-container">$Z/mZ$</span> in depth <span class="math-container">$d+1$</span>, so we have that depth-3 exponential-sized <span class="math-container">$CC^0[m]$</span> circuits can compute arbitrary decision problems over <span class="math-container">$Z/mZ$</span>. However, this still leaves open the case of depth-2 exponential-sized <span class="math-container">$CC^0[m]$</span> circuits with inputs from <span class="math-container">$Z/mZ$</span>.</p>
<h3>Question</h3>
<p>Assuming <span class="math-container">$m$</span> is composite with at least 2 distinct prime factors, does there exist some decision problem over the alphabet <span class="math-container">$Z/mZ$</span> that cannot be computed by exponential-sized depth-2 <span class="math-container">$CC^0[m]$</span> circuits with generalized gates?</p>

CC BY-SA 4.0
2021-09-29T20:07:25.243Z
I suppose you are still assuming $m$ has at least two distinct prime divisors?
Emil Jeřábek
CC BY-SA 4.0
2021-09-29T20:33:05.977Z
@EmilJeřábek Ah, yes, sorry for any confusion.
Jake
<circuit-complexity><universal-computation>
Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?
Jake
# Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?

(Asked by: username_0 on 2021-09-29)

### 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?

**Tags:** circuit-complexity, universal-computation

> **Comments:**
> **username_1**: I suppose you are still assuming $m$ has at least two distinct prime divisors?  
> **username_0**: @EmilJeřábek Ah, yes, sorry for any confusion.  

---

## 1 answers

### Answer by username_0 on 2021-11-17. Score: 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.


---

