  We consider the fundamental problem of constructing fast and small circuits
for binary addition. We propose a new algorithm with running time $\mathcal O(n
\log_2 n)$ for constructing linear-size $n$-bit adder circuits with a
significantly better depth guarantee compared to previous approaches: Our
circuits have a depth of at most $\log_2 n + \log_2 \log_2 n + \log_2 \log_2
\log_2 n + \text{const}$, improving upon the previously best circuits by [12]
with a depth of at most $\log_2 n + 8 \sqrt{\log_2 n} + 6 \log_2 \log_2 n +
\text{const}$. Hence, we decrease the gap to the lower bound of $\log_2 n +
\log_2 \log_2 n + \text{const}$ by [5] significantly from $\mathcal O
(\sqrt{\log_2 n})$ to $\mathcal O(\log_2 \log_2 \log_2 n)$.
  Our core routine is a new algorithm for the construction of a circuit for a
single carry bit, or, more generally, for an And-Or path, i.e., a Boolean
function of type $t_0 \lor ( t_1 \land (t_2 \lor ( \dots t_{m-1}) \dots ))$. We
compute linear-size And-Or path circuits with a depth of at most $\log_2 m +
\log_2 \log_2 m + 0.65$ in time $\mathcal O(m \log_2 m)$. These are the first
And-Or path circuits known that, up to an additive constant, match the lower
bound by [5] and at the same time have a linear size. The previously fastest
And-Or path circuits are only by an additive constant worse in depth, but have
a much higher size in the order of $\mathcal O (m \log_2 m)$.
