<h2>Background</h2>
<p>What is currently known for depth-2 <span class="math-container">$CC^0$</span> circuits with restricted gate types:</p>
<ul>
<li>In [1] it is shown that <span class="math-container">$(MOD_p)^k \circ MOD_m$</span> circuits (that is, <span class="math-container">$k$</span> layers of <span class="math-container">$MOD_p$</span> gates at the output) for prime power <span class="math-container">$p$</span>, arbitrary <span class="math-container">$m$</span>, and constant <span class="math-container">$k$</span> require exponential size to compute <span class="math-container">$OR$</span> or <span class="math-container">$AND$</span> over <span class="math-container">$n$</span> variables.</li>
<li>In [2] it is shown that <span class="math-container">$MOD_m \circ MOD_m$</span> circuits for arbitrary <span class="math-container">$m$</span> require exponential size to compute <span class="math-container">$OR$</span> when the accepting set of the output gate is a singleton (or <span class="math-container">$AND$</span> when the accepting set of the output gate is the complement of a singleton).</li>
</ul>
<p>The missing link here is exponential lower bounds where the first layer has a prime modulus and the second layer has a composite modulus (and we allow generalized gates with arbitrary accepting sets, to avoid the lower bound of [2]).</p>
<p>For partial progress in this direction, it seems the result of [1] can be extended to give lower bounds against <span class="math-container">$MOD_{2p} \circ MOD_2$</span> circuits for prime <span class="math-container">$p \geq 3$</span>: let <span class="math-container">$AND_{O(1)}$</span> and <span class="math-container">$OR_{O(1)}$</span> be <span class="math-container">$AND$</span> and <span class="math-container">$OR$</span> layers respectively with constant fanin on the gates; then we have:</p>
<p><span class="math-container">$$MOD_{2p} \circ MOD_2 = OR_{O(1)} \circ AND_{O(1)} \circ (MOD_p \circ MOD_2, MOD_2 \circ MOD_2)$$</span></p>
<p>We can replace the constant-fanin <span class="math-container">$AND$</span> and <span class="math-container">$OR$</span> gates with constant-depth <span class="math-container">$MOD_p$</span> circuits. Importantly, <span class="math-container">$MOD_2 \circ MOD_2 = MOD_2$</span> with no size blowup. So, our resulting class is contained in:
<span class="math-container">$$= (MOD_p)^k \circ (MOD_p)^k \circ(MOD_p \circ MOD_2, MOD_2)$$</span></p>
<p>...which is then contained in <span class="math-container">$(MOD_p)^{2k+1} \circ MOD_2$</span>, which by [1] requires exponential size to compute <span class="math-container">$AND$</span> or <span class="math-container">$OR$</span>.</p>
<p>However, this argument breaks down as soon as our <span class="math-container">$MOD$</span> gates have more than 2 prime factors, or even as soon as one of them isn't <span class="math-container">$2$</span>, since <span class="math-container">$MOD_p \circ MOD_p \neq MOD_p$</span> for <span class="math-container">$p \neq 2$</span>. It seems (strangely) that <span class="math-container">$MOD_6 \circ MOD_2$</span> circuits are known to be weak, but <span class="math-container">$MOD_6 \circ MOD_3$</span> circuits aren't.</p>
<h2>Question</h2>
<p>Does the above argument have a hidden exponential blowup somehwere? Have I just missed an important paper? Does anyone know of any lower bounds for <span class="math-container">$OR$</span> or <span class="math-container">$AND$</span> against <span class="math-container">$MOD_6 \circ MOD_3$</span> circuits?</p>
<h2>References</h2>
<p>[1] : <em>Barrington, David A. Mix; Straubing, Howard; Thérien, Denis</em>, <a href="https://doi.org/10.1016/0890-5401(90)90007-5" rel="noreferrer"><strong>Non-uniform automata over groups</strong></a>, Inf. Comput. 89, No. 2, 109-132 (1990). <a href="https://zbmath.org/?q=an:0727.68070" rel="noreferrer">ZBL0727.68070</a>.</p>
<p>[2]: <em>Caussinus, Hervé</em>, <a href="https://doi.org/10.1016/0020-0190(96)00029-4" rel="noreferrer"><strong>A note on a theorem of Barrington, Straubing and Thérien</strong></a>, Inf. Process. Lett. 58, No. 1, 31-33 (1996). <a href="https://zbmath.org/?q=an:0875.68426" rel="noreferrer">ZBL0875.68426</a>.</p>

CC BY-SA 4.0
2023-03-08T17:13:54.177Z
A note: in the non-generalized basis case, one can do the following trick. You can simulate MOD6 of MOD3 with w wires by MOD6 of MOD6 with 2w wires: double each input going into each MOD3 gate. So the depth-2 MOD6 lower bounds apply to MOD6 of MOD3 just as well.

You could also look at (for example) MOD6 of MOD7. These circuits can be simulated by MOD42 of MOD42, by a similar trick. But the trick doesn't apply when the gates allow arbitrary acceptance sets.
Ryan Williams
CC BY-SA 4.0
2023-03-13T22:34:27.680Z
The question seems to be related to the Constant Degree Hypothesis put forward in [1].
Jake
<circuit-complexity><lower-bounds>
Are exponential lower bounds known against $MOD_6 \circ MOD_3$ circuits computing $OR$?
Jake
# Are exponential lower bounds known against $MOD_6 \circ MOD_3$ circuits computing $OR$?

(Asked by: username_0 on 2023-03-07)

## Background

What is currently known for depth-2 $CC^0$ circuits with restricted gate types:

* In [1] it is shown that $(MOD\_p)^k \circ MOD\_m$ circuits (that is, $k$ layers of $MOD\_p$ gates at the output) for prime power $p$, arbitrary $m$, and constant $k$ require exponential size to compute $OR$ or $AND$ over $n$ variables.
* In [2] it is shown that $MOD\_m \circ MOD\_m$ circuits for arbitrary $m$ require exponential size to compute $OR$ when the accepting set of the output gate is a singleton (or $AND$ when the accepting set of the output gate is the complement of a singleton).

The missing link here is exponential lower bounds where the first layer has a prime modulus and the second layer has a composite modulus (and we allow generalized gates with arbitrary accepting sets, to avoid the lower bound of [2]).

For partial progress in this direction, it seems the result of [1] can be extended to give lower bounds against $MOD\_{2p} \circ MOD\_2$ circuits for prime $p \geq 3$: let $AND\_{O(1)}$ and $OR\_{O(1)}$ be $AND$ and $OR$ layers respectively with constant fanin on the gates; then we have:

$$MOD\_{2p} \circ MOD\_2 = OR\_{O(1)} \circ AND\_{O(1)} \circ (MOD\_p \circ MOD\_2, MOD\_2 \circ MOD\_2)$$

We can replace the constant-fanin $AND$ and $OR$ gates with constant-depth $MOD\_p$ circuits. Importantly, $MOD\_2 \circ MOD\_2 = MOD\_2$ with no size blowup. So, our resulting class is contained in:
$$= (MOD\_p)^k \circ (MOD\_p)^k \circ(MOD\_p \circ MOD\_2, MOD\_2)$$

...which is then contained in $(MOD\_p)^{2k+1} \circ MOD\_2$, which by [1] requires exponential size to compute $AND$ or $OR$.

However, this argument breaks down as soon as our $MOD$ gates have more than 2 prime factors, or even as soon as one of them isn't $2$, since $MOD\_p \circ MOD\_p \neq MOD\_p$ for $p \neq 2$. It seems (strangely) that $MOD\_6 \circ MOD\_2$ circuits are known to be weak, but $MOD\_6 \circ MOD\_3$ circuits aren't.

## Question

Does the above argument have a hidden exponential blowup somehwere? Have I just missed an important paper? Does anyone know of any lower bounds for $OR$ or $AND$ against $MOD\_6 \circ MOD\_3$ circuits?

## References

[1] : *Barrington, David A. Mix; Straubing, Howard; Thérien, Denis*, [**Non-uniform automata over groups**](https://doi.org/10.1016/0890-5401(90)90007-5), Inf. Comput. 89, No. 2, 109-132 (1990). [ZBL0727.68070](https://zbmath.org/?q=an:0727.68070).

[2]: *Caussinus, Hervé*, [**A note on a theorem of Barrington, Straubing and Thérien**](https://doi.org/10.1016/0020-0190(96)00029-4), Inf. Process. Lett. 58, No. 1, 31-33 (1996). [ZBL0875.68426](https://zbmath.org/?q=an:0875.68426).

**Tags:** circuit-complexity, lower-bounds

> **Comments:**
> **username_1**: A note: in the non-generalized basis case, one can do the following trick. You can simulate MOD6 of MOD3 with w wires by MOD6 of MOD6 with 2w wires: double each input going into each MOD3 gate. So the depth-2 MOD6 lower bounds apply to MOD6 of MOD3 just as well.  You could also look at (for example) MOD6 of MOD7. These circuits can be simulated by MOD42 of MOD42, by a similar trick. But the trick doesn't apply when the gates allow arbitrary acceptance sets.  
> **username_0**: The question seems to be related to the Constant Degree Hypothesis put forward in [1].  

---

## 0 answers

