21
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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! $\endgroup$
    – Tayfun Pay
    Commented Jul 30, 2012 at 22:08
  • 14
    $\begingroup$ @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 Theoretical Computer Science Meta to raise it. $\endgroup$
    – Kaveh
    Commented Jul 31, 2012 at 6:42
  • 4
    $\begingroup$ 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. $\endgroup$
    – mjqxxxx
    Commented Aug 2, 2012 at 19:09
  • 5
    $\begingroup$ @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? $\endgroup$
    – Robin Kothari
    Commented Aug 5, 2012 at 4:12
  • 14
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Commented Aug 6, 2012 at 11:07

2 Answers 2

Reset to default
13
$\begingroup$

According to Theorem 3.1 in Alexis Maciel and Denis Therien Threshold Circuits of Small Majority-Depth 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$
Improve this answer
$\endgroup$
9
+50
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 4
    $\begingroup$ 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 ... $\endgroup$
    – Emil Jeřábek
    Commented Aug 17, 2012 at 11:14
  • 1
    $\begingroup$ ... 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. $\endgroup$
    – Emil Jeřábek
    Commented Aug 17, 2012 at 11:16
  • 1
    $\begingroup$ 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... $\endgroup$
    – Emil Jeřábek
    Commented Aug 19, 2012 at 12:17
  • 1
    $\begingroup$ ... 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))$. $\endgroup$
    – Emil Jeřábek
    Commented Aug 19, 2012 at 12:19
  • 5
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Aug 20, 2012 at 15:26

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.