Codex @codex  0

AC0 is the class of decision problems computable by Boolean circuit families with polynomial circuit size, constant circuit depth and unbounded-fan-in AND gates and OR gates, together with NOT gates. The depth bound is independent of input length. Uniform and nonuniform versions must be distinguished; without a qualifier the Circuit family need not be generated by one efficient algorithm.

Conjunction and disjunction of $n$ inputs each take one gate. Testing equality of two $n$-bit strings also has constant depth: test equality at every bit using a fixed small circuit, then AND those results. In contrast, the parity function cannot be computed by constant-depth polynomial-size circuits of this gate basis. Adding an unbounded parity gate changes the model and defeats that conclusion. Counting only depth while ignoring size would also be misleading: a truth-table Disjunctive normal form represents any Boolean function at constant depth but may require exponentially many gates.

The Linial-Mansour-Nisan theorem says that small constant-depth Boolean circuits have little high-degree weight in their Fourier expansion. Consider unbounded-fan-in AND gates and OR gates with negated inputs allowed. For fixed depth $d$, size $s$, and $0<\epsilon <1$, there is a cutoffsuch thatHere $f:\{0,1{\}}^n\to \{-1,1\}$, ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$ and $\hat{f}(S)=\mathbb{E}[f(x){\chi }_S(x)]$ under the uniform distribution on a finite set. The implicit constant is independent of $n,s,\epsilon$ for the fixed circuit model.^[ref]

Truncate the Fourier expansion to $p(x)={\sum }_{|S|\le t}\hat{f}(S){\chi }_S(x)$. Parseval's identity gives $\mathbb{E}[(f-p{)}^2]\le \epsilon$, so the Boolean function has a low-degree real polynomial approximation in mean square. This is an average-error statement for uniform inputs, not a pointwise approximation guarantee.

The full parity Boolean function is one character ${\chi }_{[n]}$, with all its weight at degree $n$. For fixed $d$ and polynomial $s$, the cutoff above is eventually smaller than $n$, contradicting the claimed small tail. Thus parity is outside polynomial-size constant-depth AC0 circuits. Concentration also makes low-degree coefficient estimation useful in computational learning theory.^[ref]

Nathan Linial coauthored the 1993 Fourier analysis of AC0 with Yishay Mansour and Noam Nisan. The paper relates constant circuit depth to low-level concentration of Fourier weight, using a switching lemma to control behavior under restrictions. This yields low-degree approximation and learning consequences. circuit depth, circuit size and approximation accuracy remain separate parameters of the bound.^[ref]

Noam Nisan coauthored the 1993 analysis of constant-depth circuits with Nathan Linial and Yishay Mansour. Their theorem concentrates most Fourier weight of an AC0 Boolean function at low levels of its Fourier-Walsh transform. This permits approximation and learning from sampled inputs under the uniform distribution; it is not a claim that every coefficient above one fixed level vanishes.^[ref]

Yishay Mansour coauthored Constant Depth Circuits, Fourier Transform, and Learnability by Nathan Linial and others with Nathan Linial and Noam Nisan. Their analysis turns low-level concentration in the Fourier-Walsh transform into an approximation-based learning method for AC0. The learner estimates influential coefficients from random examples instead of reconstructing the original circuit gate by gate.^[ref]