It is well-known that every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be realized using a boolean circuit of depth 2 (over the variables, their negation and constant values) containing AND gates in the first level and one single OR gate in the upper level; this is simply the DNF representation of $f$.

Another type of gate which is of great interest in circuit complexity is the $MOD_m$ gate. The usual definition is the following:

$$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{ 1 & if \(\sum x_i \equiv 0 \mod m\) \\ 0 & if \(\sum x_i \not\equiv 0 \mod m\) \\ }$$

These gates sometimes have surprising power; for example, any boolean function can be represented by a depth-2 circuit having only $\mathrm{MOD}_6$ gates (this is folklore but I can elaborate is someone is interested).

However, another folklore is that circuits with a single OR gate at the top and $\mathrm{MOD}_m$ gates in the bottom layer (with $m$ being fixed once and for all, and in particular being the same for all the gates) is not universal, i.e. for any value of $m$, there are boolean functions that cannot be computed by $\mathrm{OR} \circ \mathrm{MOD}_m$ circuit.

I'm looking for a proof for this claim, or at least some direction.

  • 1
    $\begingroup$ In the first paragraph, either you need NOT gates or you have to say “every monotone Boolean function.” $\endgroup$ May 27, 2012 at 12:44
  • $\begingroup$ You are correct; the usual assumption is that you have as inputs the variables, their negation and also arbitrary values (important for modgates). I'll write this explicitly. $\endgroup$
    – Gadi A
    May 27, 2012 at 12:46
  • 1
    $\begingroup$ I guess that $n$, the number of input variables, is different from $n$, the modulus? $\endgroup$ May 27, 2012 at 15:45
  • $\begingroup$ Yes, sorry about that. $\endgroup$
    – Gadi A
    May 27, 2012 at 16:10
  • $\begingroup$ I am interested on this. Do you know some reference for the first folkloric fact? I wonder, if in the latter class of circuits you only allow one OR, how many do you allow in the former? $\endgroup$ May 28, 2012 at 12:01

1 Answer 1


The Boolean AND function can not be computed. Suppose actually that the AND function is computed by an $\text{OR} \circ \text{MOD}$ circuit. Then it follows that one of the MOD subcircuits must compute then AND function already, which is impossible.

  • $\begingroup$ No, he's correct. The implicit assumption here is that n is constant and we should be able to handle an arbitrarily large number of inputs with mod_n gates. $\endgroup$
    – Gadi A
    May 27, 2012 at 16:20
  • $\begingroup$ @GadiA Ah, ok. This wasn't clear in your question, at least to people who aren't familiar with the field. I've made a minor edit that should clarify this. $\endgroup$ May 27, 2012 at 16:28
  • $\begingroup$ Yes, my question was very badly phrased, sorry. $\endgroup$
    – Gadi A
    May 27, 2012 at 16:29
  • $\begingroup$ @Gilles Can you explain me what fan-in here we consider ? The problem for me is that I can't see why subcircuit of MOD can't compute AND ? How many inputs has this MOD and this AND ? $\endgroup$
    – user54001
    Apr 27, 2017 at 17:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.