Victor Lecomte

Optimal Shallow Circuits for Majority

Four decades on, H{\aa}stad's classical $2^{\Omega(n^{1/(d-1)})}$ lower bound for depth-$d$ circuits computing Parity remains the best known $\mathrm{AC}^0$ circuit lower bound for any explicit function. Majority has long been a compelling candidate for stronger lower bounds: the most natural circuits computing it are...