3
$\begingroup$

I am trying to show that the sum of $\log n$ $n$-bit integers can be computed in $\mathsf{AC^0}$. I know that the iterated addition is computable by fan-in $2$ circuits of depth $O(\log n)$, so the sum of $n$ $n$-bit integers is in $\mathsf{NC^1}$. This means that the bound is very tight. I found somes notes here which show that the iterated sum of $n$ $n$-bit integers actually lies in $\mathsf{TC^0}$.

Any help or hint on the subject would be greatly appreciated.

$\endgroup$

1 Answer 1

3
$\begingroup$

Here is a proof sketch. We use the fact that any function on $O(\log n)$ bits can be computed in depth 2 and polynomial size.

  1. The input is $\log n$ integers of length $n$, which we can think of as an $n\times \log n$ matrix.

  2. Sum the columns of the matrix to get a vector of length $n$ in which each entry has length $\log\log n$. We can also think of this as a staggered sum of $n$ numbers of length $\log \log n$, which is equivalent to the original sum.

  3. Divide the staggering sum into blocks of length $\log n/\log\log n$, by possibly dividing each summand into two parts. Each block contains $\log n/\log\log n$ summands of length $\log\log n$. Sum each block to obtain a result of length at most $2\log\log n \leq \log n/\log\log n$ (for large enough $n$). We can think of this as a new staggering sum.

  4. Repeat the previous construction. Now each block contains two summands, so the result is of length $\log n/\log\log n + 1$.

  5. Again divide into blocks. This time each block contains the sum of a full length ($\log n/\log\log n$) integer $x$ and one extra bit (a least significant bit) $y$. The actual sum also includes an extra carry bit $z$ which depends on the less significant blocks. If we could determine $z$ then we could determine the value of the sum in that block.

  6. It remains to show how to calculate the carry bit coming from the addition of blocks $B_k,\ldots,B_0$ (most significant to least significant). Suppose that in block $B_i$ we are adding $x_i$ to the bit $y_i$. Let $M$ be a block full of 1s. There is carry iff for some $i$, $x_k + y_k = x_{k-1} + y_{k-1} = x_{i+1} + y_{i+1} = M$ and $x_i + y_i = M + 1$.

If you have trouble with the proof sketch (which I haven't described very clearly), try using diagrams. The idea is to start with the initial sum and replace it with progressively simpler but equivalent sums, until the final sum can be computed in one go.

$\endgroup$
3
  • $\begingroup$ Could you clarify what $z$ is? $\endgroup$
    – iHubble
    Feb 27, 2015 at 5:48
  • $\begingroup$ The extra bit $z$ is carry from the less significant blocks. For example, when adding $28$ and $35$, we have to add $8+5$ and then $2+3+1$; here $1$ is the carry digit. $\endgroup$ Feb 27, 2015 at 5:53
  • $\begingroup$ Thank you for your quick response and for your solution sketch. $\endgroup$
    – iHubble
    Feb 27, 2015 at 6:29

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.