<p>This gate-elimination lower bound does not match Marzio’s upper bound, but it’s a start.</p>

<blockquote>
  <p><strong>Proposition:</strong> Every unbounded fan-in AND/OR/NOT circuit computing parity on $n\ge2$ variables contains at least $2n-1$ AND and OR gates.</p>
</blockquote>

<p>For convenience, I will use a model where the only gates are AND-gates, but we allow negation wires. It is easy to see that $3$ gates are necessary for $n=2$, hence it is enough to show that if $C$ is a minimal-size circuit computing parity on $n&gt;2$ variables, we can find a restriction of one variable which kills at least two gates.</p>

<p>If some variable $x_i$ has at least two positive parents (i.e., it is connected by unnegated wires to two different gates), setting this variable to $0$ will kill the parents and we are done; likewise if it has two negative parents. We may thus assume that each variable has at most one positive and at most one negative parent.</p>

<p>Let $a$ be a bottom-level gate in the circuit. Without loss of generality, $a=x_1\land x_2\land\cdots$. Set $x_1=0$, which forces $a=0$ and kills it. The restricted circuit $C'$ still computes parity, in particular it depends on $x_2$, hence $x_2$ has a negative parent $b=\neg x_2\land c_1\land\dots\land c_r$. Notice that in $C'$, no $c_j$ depends on $x_2$. If there were an assignment to $x_3,\dots,x_n$ which (on top of $x_1=0$) makes some $c_j$ false, the circuit restricted by this assignment would be constant, contradicting the fact that it computes $x_2$ or $\neg x_2$. Thus, in $C'$, all the $c_j$ compute constant $1$, and $b$ computes $\neg x_2$, hence we can eliminate it along with $a$.</p>

<p>EDIT: As I learned from Yuri Kombarov’s paper, this $2n-1$ lower bound, as well as the $\lfloor\frac52n\rfloor-2$ upper bound implied by Marzio De Biasi’s answer, were originally proved in</p>

<p>[1] Ingo Wegener, <em>The complexity of the parity function in unbounded fan-in, unbounded depth circuits</em>, Theoretical Computer Science 85 (1991), no. 1, pp. 155–170. <a href="http://dx.doi.org/10.1016/0304-3975(91)90052-4" rel="nofollow">http://dx.doi.org/10.1016/0304-3975(91)90052-4</a></p>

CC BY-SA 3.0
2014-10-19T19:57:24.433Z
Yes, so the question is if we can eliminate 5 gates by fixing 2 variables.
domotorp
CC BY-SA 3.0
2014-10-19T21:50:55.190Z
Right. Or even better, if we can eliminate 3 gates by fixing one variable when $n$ is even.
Emil Jeřábek
CC BY-SA 3.0
2014-10-19T19:35:43.767Z
2016-01-25T17:15:42.047Z
2016-01-25T17:15:42.047Z
Emil Jeřábek
<p>I expand my comment: </p>

<p>1) a  fan-in $k$ AND gate can be simulated by $k-1$ fan-in 2 AND gates (and the same applies to an OR gate); so if $I_i \geq 2$ is the fan-in of gate $g_i$ the following relation must hold:</p>

<p>$$|C| + \sum_i (I_i - 2) \geq 3(n-1)$$</p>

<p>2) if you allow <em>arbitrary fan in</em> then you can beat the $3(n-1)$ bound; for example consider the PARITY on 3 variables $(x_1,x_2,x_3)$; the following circuit computes it with only 5 arbitrary fan-in gates:</p>

<p><img src="https://i.sstatic.net/YvfMu.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-10-18T21:41:46.940Z
Nice, indeed for n=3 the CNF has only 5 gates! I wonder if one can do even better in general.
domotorp
CC BY-SA 3.0
2014-10-18T22:36:39.370Z
I didn't think about it too much, but you can surely combine and use in parallel the above circuit and get, for example, a PARITY circuit for 9 variables that uses only 20 gates instead of 24
Marzio De Biasi
CC BY-SA 3.0
2014-10-19T11:55:51.037Z
I did and I've updated my question.
domotorp
CC BY-SA 3.0
2014-10-18T19:51:11.110Z
2014-10-18T20:06:30.987Z
2014-10-18T20:06:30.987Z
Marzio De Biasi
<p>This is an extended comment to show what Emil's argument gives if we try proving the $5n/2$ bound. Here we can try to eliminate 3 gates with one variable or 5 gates with two variables.</p>

<p>If there is a literal with 3 parents, we can eliminate all 3 with one variable.</p>

<p>If two literals occur together in 2 different gates, together, we can apply the main argument from Emil's answer, again eliminating 3 gates with one variable.</p>

CC BY-SA 3.0
2014-10-20T12:47:32.830Z
2014-10-20T12:47:32.830Z
domotorp
<p>It is possible to compute parity using only 2.33n + C  gates. The construction is quite simple and is given in this article.</p>

<p><a href="http://link.springer.com/article/10.3103/S0027132215050083" rel="nofollow noreferrer">http://link.springer.com/article/10.3103/S0027132215050083</a></p>

<p>Here is an example of a circuit for parity of 6 variables using only 12 gates (each gate is an AND-gate, a circle near the input of a gate means that this input is inverted). Note that a circuit for parity of 6 variables that is constructed by stacking DNF-blocks (like in Marzio’s upper bound) consists of 13 gates.</p>

<p>I have checked that for n=2,3,4,5,6 sizes of optimal circuits are 3,5,8,10,12. These values are also sizes of circuits that give 2.33n upper bound. I still don’t know if 2.33n is the size of optimal circuit for every n. Even more, I don’t know the size of optimal circuit for parity of 7 variables (there are two possible values, 14 and 15).
<a href="https://i.sstatic.net/W7IuT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/W7IuT.png" alt="Circuit for patity of 6 variables"></a></p>

CC BY-SA 3.0
2016-01-24T14:04:10.803Z
2016-01-25T07:27:12.143Z
2016-01-25T07:27:12.143Z
Yuri Kombarov
<p>It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp.
(We define size as the number of AND and OR gates.)
The proof is by gate-elimination and it seems to fail if we allow arbitrary fan-in.
What is known for this case?</p>

<p>Specifically, does anyone know an example when larger fan-in helps, i.e., we need less than $3(n-1)$ gates?</p>

<p><strong>Update Oct 18.</strong> Marzio has shown that for $n=3$ even $5$ gates suffice using the CNF form of PARITY. This implies a bound of $\lfloor \frac 52 n \rfloor-2$ for general $n$. Can YOU do better?</p>

CC BY-SA 3.0
2014-10-12T09:34:48.243Z
[This paper](http://arxiv.org/abs/1410.2456) may be related. The basis, however, here is much larger than AND, OR.
Stasys
CC BY-SA 3.0
2014-10-15T18:18:31.990Z
The following answer is (remotely) related to your question. http://cstheory.stackexchange.com/questions/3624/practical-consequences-of-parity-notin-ac0?rq=1
Hermann Gruber
CC BY-SA 3.0
2014-10-18T00:24:25.197Z
Not a great intuition: every AND (OR) with fan-in $k$ can be simulated by $k-1$ fan-in 2 ANDs (ORs); so we have $|C| + \sum d_i \geq 3(n-1)$  where $d_i$ is equal to the inputs of gate $g_i$ - 2.
Marzio De Biasi
CC BY-SA 3.0
2014-10-19T16:05:35.343Z
In both the $3n$ and $\frac52n$ upper bounds, you are actually ignoring negations *everywhere* rather than just on variables, right?
Emil Jeřábek
CC BY-SA 3.0
2014-10-19T17:36:15.133Z
@Emil: It makes no difference, as you can always push them to the bottom using De Morgan.
domotorp
CC BY-SA 3.0
2014-10-19T17:52:09.610Z
How do you do that without duplicating the gate in case it is used both positively and negatively?
Emil Jeřábek
CC BY-SA 3.0
2014-10-19T19:28:49.173Z
@Emil: Good point! I reedit my question, thx!
domotorp
CC BY-SA 3.0
2014-10-21T14:45:19.320Z
Maybe it is trivial, but since it is not mentioned: $PARITY\in \mathrm{NC^1}$ but  $PARITY\notin \mathrm{AC^0}$. Sorry if I missed something @mario, but a  fan-in $k$ gate can be simulated with $logk$ fan-in 2 gates, not $k-1$.
Harry
CC BY-SA 3.0
2014-10-21T21:39:44.193Z
@Harry: You need k-1 fan-in gates, but they can be placed in depth $\log k$. This question is about SIZE and not DEPTH!
domotorp
CC BY-SA 3.0
2017-06-19T21:53:41.900Z
Would you please provide a reference for the 3(n-1) lower bound?
Dandelion
<cc.complexity-theory><circuit-complexity><parity>
What is the minimum size of a circuit that computes PARITY?
domotorp
# What is the minimum size of a circuit that computes PARITY?

(Asked by: username_0 on 2014-10-10)

It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp.
(We define size as the number of AND and OR gates.)
The proof is by gate-elimination and it seems to fail if we allow arbitrary fan-in.
What is known for this case?

Specifically, does anyone know an example when larger fan-in helps, i.e., we need less than $3(n-1)$ gates?

**Update Oct 18.** Marzio has shown that for $n=3$ even $5$ gates suffice using the CNF form of PARITY. This implies a bound of $\lfloor \frac 52 n \rfloor-2$ for general $n$. Can YOU do better?

**Tags:** cc.complexity-theory, circuit-complexity, parity
> **Comments:**
> **username_1**: [This paper](http://arxiv.org/abs/1410.2456) may be related. The basis, however, here is much larger than AND, OR.  
> **username_2**: The following answer is (remotely) related to your question. http://cstheory.stackexchange.com/questions/3624/practical-consequences-of-parity-notin-ac0?rq=1  
> **username_3**: Not a great intuition: every AND (OR) with fan-in $k$ can be simulated by $k-1$ fan-in 2 ANDs (ORs); so we have $|C| + \sum d_i \geq 3(n-1)$  where $d_i$ is equal to the inputs of gate $g_i$ - 2.  
> **username_4**: In both the $3n$ and $\frac52n$ upper bounds, you are actually ignoring negations *everywhere* rather than just on variables, right?  
> **username_0**: @Emil: It makes no difference, as you can always push them to the bottom using De Morgan.  
> **username_4**: How do you do that without duplicating the gate in case it is used both positively and negatively?  
> **username_0**: @Emil: Good point! I reedit my question, thx!  
> **username_5**: Maybe it is trivial, but since it is not mentioned: $PARITY\in \mathrm{NC^1}$ but  $PARITY\notin \mathrm{AC^0}$. Sorry if I missed something @mario, but a  fan-in $k$ gate can be simulated with $logk$ fan-in 2 gates, not $k-1$.  
> **username_0**: @Harry: You need k-1 fan-in gates, but they can be placed in depth $\log k$. This question is about SIZE and not DEPTH!  
> **username_6**: Would you please provide a reference for the 3(n-1) lower bound?  

---

## 4 answers

### Answer by username_7 on 2016-01-24. Score: 10 | Accepted answer

It is possible to compute parity using only 2.33n + C gates. The construction is quite simple and is given in this article.

<http://link.springer.com/article/10.3103/S0027132215050083>

Here is an example of a circuit for parity of 6 variables using only 12 gates (each gate is an AND-gate, a circle near the input of a gate means that this input is inverted). Note that a circuit for parity of 6 variables that is constructed by stacking DNF-blocks (like in Marzio’s upper bound) consists of 13 gates.

I have checked that for n=2,3,4,5,6 sizes of optimal circuits are 3,5,8,10,12. These values are also sizes of circuits that give 2.33n upper bound. I still don’t know if 2.33n is the size of optimal circuit for every n. Even more, I don’t know the size of optimal circuit for parity of 7 variables (there are two possible values, 14 and 15).
[![Circuit for patity of 6 variables](https://i.sstatic.net/W7IuT.png)](https://i.sstatic.net/W7IuT.png)


---

### Answer by username_4 on 2014-10-19. Score: 10

This gate-elimination lower bound does not match Marzio’s upper bound, but it’s a start.

> **Proposition:** Every unbounded fan-in AND/OR/NOT circuit computing parity on $n\ge2$ variables contains at least $2n-1$ AND and OR gates.

For convenience, I will use a model where the only gates are AND-gates, but we allow negation wires. It is easy to see that $3$ gates are necessary for $n=2$, hence it is enough to show that if $C$ is a minimal-size circuit computing parity on $n>2$ variables, we can find a restriction of one variable which kills at least two gates.

If some variable $x\_i$ has at least two positive parents (i.e., it is connected by unnegated wires to two different gates), setting this variable to $0$ will kill the parents and we are done; likewise if it has two negative parents. We may thus assume that each variable has at most one positive and at most one negative parent.

Let $a$ be a bottom-level gate in the circuit. Without loss of generality, $a=x\_1\land x\_2\land\cdots$. Set $x\_1=0$, which forces $a=0$ and kills it. The restricted circuit $C'$ still computes parity, in particular it depends on $x\_2$, hence $x\_2$ has a negative parent $b=\neg x\_2\land c\_1\land\dots\land c\_r$. Notice that in $C'$, no $c\_j$ depends on $x\_2$. If there were an assignment to $x\_3,\dots,x\_n$ which (on top of $x\_1=0$) makes some $c\_j$ false, the circuit restricted by this assignment would be constant, contradicting the fact that it computes $x\_2$ or $\neg x\_2$. Thus, in $C'$, all the $c\_j$ compute constant $1$, and $b$ computes $\neg x\_2$, hence we can eliminate it along with $a$.

EDIT: As I learned from Yuri Kombarov’s paper, this $2n-1$ lower bound, as well as the $\lfloor\frac52n\rfloor-2$ upper bound implied by Marzio De Biasi’s answer, were originally proved in

[1] Ingo Wegener, *The complexity of the parity function in unbounded fan-in, unbounded depth circuits*, Theoretical Computer Science 85 (1991), no. 1, pp. 155–170. <http://dx.doi.org/10.1016/0304-3975(91)90052-4>

> **Comments:**
> **username_0**: Yes, so the question is if we can eliminate 5 gates by fixing 2 variables.  
> **username_4**: Right. Or even better, if we can eliminate 3 gates by fixing one variable when $n$ is even.  

---

### Answer by username_3 on 2014-10-18. Score: 8

I expand my comment:

1) a fan-in $k$ AND gate can be simulated by $k-1$ fan-in 2 AND gates (and the same applies to an OR gate); so if $I\_i \geq 2$ is the fan-in of gate $g\_i$ the following relation must hold:

$$|C| + \sum\_i (I\_i - 2) \geq 3(n-1)$$

2) if you allow *arbitrary fan in* then you can beat the $3(n-1)$ bound; for example consider the PARITY on 3 variables $(x\_1,x\_2,x\_3)$; the following circuit computes it with only 5 arbitrary fan-in gates:

![enter image description here](https://i.sstatic.net/YvfMu.png)

> **Comments:**
> **username_0**: Nice, indeed for n=3 the CNF has only 5 gates! I wonder if one can do even better in general.  
> **username_3**: I didn't think about it too much, but you can surely combine and use in parallel the above circuit and get, for example, a PARITY circuit for 9 variables that uses only 20 gates instead of 24  
> **username_0**: I did and I've updated my question.  

---

### Answer by username_0 on 2014-10-20. Score: 2

This is an extended comment to show what Emil's argument gives if we try proving the $5n/2$ bound. Here we can try to eliminate 3 gates with one variable or 5 gates with two variables.

If there is a literal with 3 parents, we can eliminate all 3 with one variable.

If two literals occur together in 2 different gates, together, we can apply the main argument from Emil's answer, again eliminating 3 gates with one variable.


---

