<p>Depth 2 circuits require exponential size to compute addition since a depth 2 circuit must be either DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms.</p>

<p><strong>Warning</strong>: the part below is <em>buggy</em>. See the comments under the answer.</p>

<p>The way I count it, addition can be done in depth 3.  Assume $a_i$ and $b_i$ are the $i$th bits of the two numbers, where $0$ is the index of the LSB and $n$ of the MSB.  </p>

<p>Let us compute the $i$th bit of the sum, $s_i$ in the standard way with carry look ahead:</p>

<p>$$s_i = a_i \oplus b_i \oplus c_i$$</p>

<p>where $\oplus$ is XOR and $c_i$ is the carry computed as:</p>

<p>$$c_i = \bigvee_{j\mid j &lt; i} (g_j \wedge p_j)$$</p>

<p>and $g_j$ means that the $j$th location "generated" the carry:</p>

<p>$$g_j = (a_j \wedge b_j)$$</p>

<p>and $p_j$ means that the carry gets propagated from $j$ to $i$:</p>

<p>$$p_j = \bigwedge_{k\mid j &lt; k &lt; i} (a_j \vee b_j)$$</p>

<p>Counting the depth, $p_j$ is depth 2, and $c_i$ is depth 3.  While it would seem that $s_i$ is depth 4 or 5, it really is also just depth 3 since it is a bounded fanin computation of depth 3 circuits so one may push the top two levels down using de-Morgan formulas, while blowing the circuit size by a polynomial amount.</p>

CC BY-SA 3.0
2012-08-17T11:14:04.320Z
I don’t quite see how bounded fanin computation of depth 3 circuits is automatically depth 3. If, say, you write $s_i$ as $(c_i\land\neg(a_i\oplus b_i))\lor(\neg c_i\land(a_i\oplus b_i))$, you can make the first disjunct a depth 3 circuit with $\bigvee$ on top, and the second disjunct a depth 3 circuit with $\bigwedge$ on top. I don’t see how to push the top disjunction down without increasing the depth by one to account for the mismatch between the connective types in the two parts. This can be remedied by noting that $c_i$ can also be computed in a different way by a depth 3 circuit ...
Emil Jeřábek
CC BY-SA 3.0
2012-08-17T11:16:31.523Z
... with $\bigwedge$ on top. On the other hand, all the depth 3 circuits have bounded bottom fan-in, so I’d call them depth 2 1/2.
Emil Jeřábek
CC BY-SA 3.0
2012-08-18T15:47:02.553Z
Take an OR of two depth d circuits with AND on the top: (x1 and ... and xn) OR (y1 and ... and yn), where each xi and yi are a depth (d-1) circuit with OR on the top.  Now use deMorgan to get the equivalent (quadratic size in the original):  (x1 or y1) AND (x1 or y2) AND ... AND (xn or yn).  However the xi's and yi's are depth d-1 circuits with OR on the top, so (xi or yj) can be merged and is still a depth (d-1) circuit and the AND of these is depth d back again.
Noam
CC BY-SA 3.0
2012-08-19T12:17:44.773Z
That's obvious. What I am pointing out is that as written, you do *not* have here an OR of two depth $d$ circuits with AND on the top. You have an OR of two depth $d$ circuits, one of which has AND on the top, and the other has OR on the top. I doubt such circuits can be converted to depth $d$ in general. Think about the polynomial fan-in ANDs and ORs as quantifiers. You can express $(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\forall x_1\exists x_2\dots Qx_d\psi(x_1,\dots,x_d))$ as a prenex formula with $d$ quantifier blocks, but you need $d+1$ blocks to express...
Emil Jeřábek
CC BY-SA 3.0
2012-08-19T12:19:18.483Z
... the formula $(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\exists x_1\forall x_2\dots \overline Qx_d\phi(x_1,\dots,x_d))$.
Emil Jeřábek
CC BY-SA 3.0
2012-08-20T15:26:44.157Z
For an explicit counterexample to the general principle, let $f_n(x_1,\dots,x_n)$ be a family of functions computable by $AC^0_d$ circuits with OR on the top requiring super-polynomial depth $d$ circuits with AND on the top (e.g., Sipser functions). Then $x_0\oplus f_n$ do not have $AC^0_d$ circuits. Assume for contradiction that $C_n(x_0,\dots,x_n)$ are such circuits, and that $C_n$ has OR on the top (the other case is symmetric). By setting $x_0=1$, we obtain $AC^0_d$ circuits for $\neg f_n$ with OR on the top, hence $AC^0_d$ circuits for $f_n$ with AND on the top, a contradiction.
Emil Jeřábek
CC BY-SA 3.0
2012-08-21T04:24:43.433Z
Oops, you are right, of course, Emil.  Thanks.
Noam
CC BY-SA 3.0
2012-08-14T06:47:28.583Z
2013-10-22T16:23:38.343Z
2013-10-22T16:23:38.343Z
Noam
<p>According to Theorem 3.1 in Alexis Maciel and Denis Therien <a href="http://dx.doi.org/10.1006/inco.1998.2732" rel="nofollow">Threshold Circuits of Small Majority-Depth</a> there is indeed a depth-3 circuit for computing the addition of two numbers. </p>

<p>The precise bound is $\Delta_2 \cdot \mathsf{NC}^0_1$ where $\Delta_2 = \Sigma_2 \cap \Pi_2$ are problems which have depth-2 $\mathsf{AC}^0$ circuits with both $\vee,\wedge$ gates at top and $\mathsf{NC}^0_1$ circuits are $\mathsf{NC}^0$ circuits of depth one (see the paper for a detailed explanation of the notation).</p>

<p>The main proof ideas are:</p>

<ul>
<li>First, express the Carry-lookahead circuit as $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$</li>
<li>Next, invoke closure properties of $\Delta_2$ to write this as $\Delta_2\cdot\mathsf{NC}^0$</li>
<li>Finally, use the fact (also proved in the paper) that $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$</li>
</ul>

CC BY-SA 3.0
2013-10-21T01:16:47.340Z
2013-10-21T16:32:39.530Z
2013-10-21T16:32:39.530Z
SamiD
<p>Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary numbers using a polynomial size circuit family with depth less than that obtained by carry look ahead algorithm? </p>

<p>Are there any super polynomial lowerbounds for the size of $AC^0_d$ circuit families computing addition where $d$ is 2 or 3?</p>

<p>By depth I mean alternation depth.</p>

CC BY-SA 3.0
2012-07-30T22:08:52.413Z
Can you tell us your name? Who you are? For the past month or so people are making a new username on here, asking a question and then deleting that user name!
Tayfun Pay
CC BY-SA 3.0
2012-07-31T06:42:34.117Z
@Geekster, generally people are not required to create an account or use their real names (however it is encouraged to do so for various reasons). If you have a general concern about something please use [meta] to raise it.
Kaveh
CC BY-SA 3.0
2012-08-02T19:09:27.127Z
This could be brute-forced by verifying that no depth-$4$ AC$^{0}$ circuit can compute the $(m+1)$-bit sum of two $m$-bit inputs for some fixed $m$; there are only finitely-many boolean functions of the input bits that can appear at each depth.
mjqxxxx
CC BY-SA 3.0
2012-08-05T04:12:50.503Z
@mjqxxxx: How do you enforce the polynomial-size constraint on AC0 circuits when brute-forcing for a fixed m? @ OP: Is the current best circuit depth 4 or depth 5?
Robin Kothari
CC BY-SA 3.0
2012-08-06T05:58:37.480Z
@RobinKothari: If there's no depth-$4$ circuit for a particular $m$, then there's no depth-$4$ circuit family for the general problem, polynomial-size or not.  (The brute force approach can only prove the negative result here.)
mjqxxxx
CC BY-SA 3.0
2012-08-06T11:07:01.500Z
@mjqxxxx: *Every* Boolean function is computable by depth $2$ circuits. Now, suppose you find for your fixed $m$ a circuit of size $s$. How do you judge whether there are size $cn$ circuits for every $n$, where $c=s/m$, or whether there are only circuits of size $2^{\epsilon n}$, where $\epsilon=(\log s)/m$? There is simply no way to infer asymptotic information from a finite example.
Emil Jeřábek
<cc.complexity-theory><circuit-complexity><lower-bounds><upper-bounds>
Can addition be carried out in less than depth 5?
Anonymous
# Can addition be carried out in less than depth 5?

(Asked by: username_0 on 2012-07-30)

Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary numbers using a polynomial size circuit family with depth less than that obtained by carry look ahead algorithm?

Are there any super polynomial lowerbounds for the size of $AC^0\_d$ circuit families computing addition where $d$ is 2 or 3?

By depth I mean alternation depth.

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, upper-bounds
> **Comments:**
> **username_1**: Can you tell us your name? Who you are? For the past month or so people are making a new username on here, asking a question and then deleting that user name!  
> **username_2**: @Geekster, generally people are not required to create an account or use their real names (however it is encouraged to do so for various reasons). If you have a general concern about something please use [meta] to raise it.  
> **username_3**: This could be brute-forced by verifying that no depth-$4$ AC$^{0}$ circuit can compute the $(m+1)$-bit sum of two $m$-bit inputs for some fixed $m$; there are only finitely-many boolean functions of the input bits that can appear at each depth.  
> **username_4**: @mjqxxxx: How do you enforce the polynomial-size constraint on AC0 circuits when brute-forcing for a fixed m? @ OP: Is the current best circuit depth 4 or depth 5?  
> **username_3**: @RobinKothari: If there's no depth-$4$ circuit for a particular $m$, then there's no depth-$4$ circuit family for the general problem, polynomial-size or not.  (The brute force approach can only prove the negative result here.)  
> **username_5**: @mjqxxxx: *Every* Boolean function is computable by depth $2$ circuits. Now, suppose you find for your fixed $m$ a circuit of size $s$. How do you judge whether there are size $cn$ circuits for every $n$, where $c=s/m$, or whether there are only circuits of size $2^{\epsilon n}$, where $\epsilon=(\log s)/m$? There is simply no way to infer asymptotic information from a finite example.  

---

## 2 answers

### Answer by username_7 on 2013-10-21. Score: 13 | Accepted answer

According to Theorem 3.1 in Alexis Maciel and Denis Therien [Threshold Circuits of Small Majority-Depth](http://dx.doi.org/10.1006/inco.1998.2732) there is indeed a depth-3 circuit for computing the addition of two numbers.

The precise bound is $\Delta\_2 \cdot \mathsf{NC}^0\_1$ where $\Delta\_2 = \Sigma\_2 \cap \Pi\_2$ are problems which have depth-2 $\mathsf{AC}^0$ circuits with both $\vee,\wedge$ gates at top and $\mathsf{NC}^0\_1$ circuits are $\mathsf{NC}^0$ circuits of depth one (see the paper for a detailed explanation of the notation).

The main proof ideas are:

* First, express the Carry-lookahead circuit as $\mathsf{NC}^0\cdot\Delta\_2\cdot\mathsf{NC}^0$
* Next, invoke closure properties of $\Delta\_2$ to write this as $\Delta\_2\cdot\mathsf{NC}^0$
* Finally, use the fact (also proved in the paper) that $\mathsf{NC}^0 \subset \Delta\_1\cdot\mathsf{NC}^0\_1$


---

### Answer by username_6 on 2012-08-14. Score: 9

Depth 2 circuits require exponential size to compute addition since a depth 2 circuit must be either DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms.

**Warning**: the part below is *buggy*. See the comments under the answer.

The way I count it, addition can be done in depth 3. Assume $a\_i$ and $b\_i$ are the $i$th bits of the two numbers, where $0$ is the index of the LSB and $n$ of the MSB.

Let us compute the $i$th bit of the sum, $s\_i$ in the standard way with carry look ahead:

$$s\_i = a\_i \oplus b\_i \oplus c\_i$$

where $\oplus$ is XOR and $c\_i$ is the carry computed as:

$$c\_i = \bigvee\_{j\mid j < i} (g\_j \wedge p\_j)$$

and $g\_j$ means that the $j$th location "generated" the carry:

$$g\_j = (a\_j \wedge b\_j)$$

and $p\_j$ means that the carry gets propagated from $j$ to $i$:

$$p\_j = \bigwedge\_{k\mid j < k < i} (a\_j \vee b\_j)$$

Counting the depth, $p\_j$ is depth 2, and $c\_i$ is depth 3. While it would seem that $s\_i$ is depth 4 or 5, it really is also just depth 3 since it is a bounded fanin computation of depth 3 circuits so one may push the top two levels down using de-Morgan formulas, while blowing the circuit size by a polynomial amount.

> **Comments:**
> **username_5**: I don’t quite see how bounded fanin computation of depth 3 circuits is automatically depth 3. If, say, you write $s_i$ as $(c_i\land\neg(a_i\oplus b_i))\lor(\neg c_i\land(a_i\oplus b_i))$, you can make the first disjunct a depth 3 circuit with $\bigvee$ on top, and the second disjunct a depth 3 circuit with $\bigwedge$ on top. I don’t see how to push the top disjunction down without increasing the depth by one to account for the mismatch between the connective types in the two parts. This can be remedied by noting that $c_i$ can also be computed in a different way by a depth 3 circuit ...  
> **username_5**: ... with $\bigwedge$ on top. On the other hand, all the depth 3 circuits have bounded bottom fan-in, so I’d call them depth 2 1/2.  
> **username_6**: Take an OR of two depth d circuits with AND on the top: (x1 and ... and xn) OR (y1 and ... and yn), where each xi and yi are a depth (d-1) circuit with OR on the top.  Now use deMorgan to get the equivalent (quadratic size in the original):  (x1 or y1) AND (x1 or y2) AND ... AND (xn or yn).  However the xi's and yi's are depth d-1 circuits with OR on the top, so (xi or yj) can be merged and is still a depth (d-1) circuit and the AND of these is depth d back again.  
> **username_5**: That's obvious. What I am pointing out is that as written, you do *not* have here an OR of two depth $d$ circuits with AND on the top. You have an OR of two depth $d$ circuits, one of which has AND on the top, and the other has OR on the top. I doubt such circuits can be converted to depth $d$ in general. Think about the polynomial fan-in ANDs and ORs as quantifiers. You can express $(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\forall x_1\exists x_2\dots Qx_d\psi(x_1,\dots,x_d))$ as a prenex formula with $d$ quantifier blocks, but you need $d+1$ blocks to express...  
> **username_5**: ... the formula $(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\exists x_1\forall x_2\dots \overline Qx_d\phi(x_1,\dots,x_d))$.  
> **username_5**: For an explicit counterexample to the general principle, let $f_n(x_1,\dots,x_n)$ be a family of functions computable by $AC^0_d$ circuits with OR on the top requiring super-polynomial depth $d$ circuits with AND on the top (e.g., Sipser functions). Then $x_0\oplus f_n$ do not have $AC^0_d$ circuits. Assume for contradiction that $C_n(x_0,\dots,x_n)$ are such circuits, and that $C_n$ has OR on the top (the other case is symmetric). By setting $x_0=1$, we obtain $AC^0_d$ circuits for $\neg f_n$ with OR on the top, hence $AC^0_d$ circuits for $f_n$ with AND on the top, a contradiction.  
> **username_6**: Oops, you are right, of course, Emil.  Thanks.  

---

