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.