# Depth-2 circuits with OR and MOD gates are not universal?

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.

• In the first paragraph, either you need NOT gates or you have to say “every monotone Boolean function.” – Tsuyoshi Ito May 27 '12 at 12:44
• 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. – Gadi A May 27 '12 at 12:46
• I guess that $n$, the number of input variables, is different from $n$, the modulus? – Kristoffer Arnsfelt Hansen May 27 '12 at 15:45
• Yes, sorry about that. – Gadi A May 27 '12 at 16:10
• 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? – Juan Bermejo Vega May 28 '12 at 12:01

## 1 Answer

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.

• 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. – Gadi A May 27 '12 at 16:20
• @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. – Gilles May 27 '12 at 16:28
• Yes, my question was very badly phrased, sorry. – Gadi A May 27 '12 at 16:29
• @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 ? – user54001 Apr 27 '17 at 17:31