Reduction for p-precision addition to uniform TC0 circuits

Merrill and Sabharwal (2022) define a $p$-precision addition operator in their paper on Log-Precision Transformers are Uniform Threshold Circuits as follows, assuming a reduction via uniform $\mathtt{TC}^0$ circuits to adding $n$ integers of size $p$ exists.

In this blog entry, I will show a reduction for this.

Definition ($p$-precision addition operator). A $p$-precision addition operator $\oplus$ is a function that maps values $x_1,\ldots,x_n$ (with each $x_i \in \{0,1\}^p$) to $s= \oplus_{i=1}^{n} \in \{0,1\}^p$, such that computing $\oplus$ can be reduced via uniform $\mathtt{TC}^0$ circuits to adding $n$ integers of size $p$.

First, we will look at an example for intuition.

Example

Let $p = 3$ and $n = 2$, and we want to compute $110 \oplus 011$ , i.e., we want to compute $5 + 3$ in binary.

Reduction

The reduction of $\oplus : A \to B$ to $g: X \to Y$ is a pair of Turing machines $M, M'$, such that,

where

• $A = ( x_1, \ldots, x_n)$, where $|x_i| = p, \forall\; 1 \leq i \leq n\,$
• $B = y$, where $|y| = p$
• $M$ is a $\mathtt{AC}^0$ circuit
• $X = \{( x^1_1, \ldots, x^1_n), \ldots, ( x^{p'}_1, \ldots, x^{p'}_n)\}$
• $Y = (y_1, \ldots, y_{p'}) = (\sum \{ x^1_1, \ldots, x^1_n \}, \ldots, \sum\{ x^{p'}_1, \ldots, x^{p'}_n\})$
• $g$ is a $\mathtt{TC}^0$ circuit (addition of integers)
• $M'$ is a $\mathtt{AC}^0$ circuit.