AC0

Remarks

Example: addition is in $\mathrm{AC}^0$, in the sense that each output bit of the sum of two $n$-bit numbers $a$ and $b$ is computed by such circuits. The carry into position $i$ is $$c_i = \bigvee_{j < i} \Big( a_j \wedge b_j \wedge \bigwedge_{j < k < i} (a_k \vee b_k) \Big),$$ which has constant depth and $O(n^2)$ gates, and the sum bit $a_i \oplus b_i \oplus c_i$ adds a constant number of layers.

Non-example: the parity language $\set{x : x \text{ has an odd number of ones}}$ has circuits of depth $O(\log n)$ and size $O(n)$ with fan-in $2$. But no choice of $p$ and $d$ satisfies clauses 2 and 3 together for it, by the theorem parity not in AC0.

The definition above is non-uniform. Uniform versions ask in addition that $C_n$ be computable from $n$ by a weak machine, such as a logarithmic-time machine; the lower bound for parity holds for both.