##
We consider the problem of adding two n-bit numbers that are chosen
independently and uniformly at random, where the adder is a circuit of
AND, OR, and NOT gates of fan-in two.

We first present a circuit that adds at least 1 - epsilon fraction of
pairs of numbers correctly and has running time loglog(n/epsilon) +
O(sqrt(loglog(n/epsilon))). We then prove that this running time is
optimal.

Next we present a circuit that always produces the correct answer. We
show that this circuit adds two n-bit numbers from the uniform
distribution in expected 1/2 logn + O(sqrt(log n)) time, a speedup
factor of two over the best possible running time of a worst-case
adder. We prove that this expected running time is optimal.