Publication
Breaking the Parity Barrier for Constant-Depth Circuits
ECCC TR26-248, 2026. PDF · Official record
Abstract
A constant-depth circuit consists of AND and OR gates of unbounded fan-in, arranged in a constant number of layers, that read the input literals; for example, a depth-three circuit is an OR of CNFs or an AND of DNFs. The classical lower bound of Håstad (1989) states that every depth-\(d\) circuit computing the parity function has \(2^{\Omega(n^{1/(d-1)})}\) gates. This parity barrier stood for decades: no explicit function was known to require depth-\(d\) circuits of size \(2^{\omega(n^{1/(d-1)})}\) for any constant \(d\). OpenAI (2026) recently announced that they broke this barrier for depth-three circuits: they gave an explicit function in P that requires OR-AND-OR circuits of size \(2^{\omega(\sqrt{n})}\).
In this paper, we break the parity barrier at every constant depth with a simpler function. We prove that for every fixed \(d \ge 3\), every depth-\(d\) circuit computing the trilinear function \(\sum_{i,j} a_{i+j} x_i y_j \bmod 2\) for \(x,y \in \{0,1\}^n\) and \(a \in \{0,1\}^{2n-1}\), requires \(2^{\Omega((n\log n/\log\log n)^{1/(d-1)})}\) gates. Our proof combines the restriction lemma of OpenAI, for which we give a short new proof, with Håstad's switching lemma and the sparsification lemma of Calabro, Impagliazzo, and Paturi (2006).