6
$\begingroup$

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, Inf. Comput. 89, No. 2, 109-132 (1990). ZBL0727.68070.

[2]: Caussinus, Hervé, A note on a theorem of Barrington, Straubing and Thérien, Inf. Process. Lett. 58, No. 1, 31-33 (1996). ZBL0875.68426.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Mar 8 at 17:13
  • $\begingroup$ The question seems to be related to the Constant Degree Hypothesis put forward in [1]. $\endgroup$
    – Jake
    Mar 13 at 22:34

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.