[Solved]: Sum of $\log n$ $n$-bit integers is in $\mathsf{AC^0}$

Problem Detail: 

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.

Asked By : iHubble

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39693

3.2K people like this

 Download Related Notes/Documents