Optimal Shallow Circuits for Majority

Abstract

Four decades on, Hå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 substantially larger than those for Parity and have repeatedly been conjectured to be optimal. We present a simple construction, found by GPT-6 Astra, of depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$ for any symmetric function. This result settles the asymptotic ${\mathrm{AC}}^0$ circuit complexity of Majority, matching Håstad's lower bound. The proof draws inspiration from well-loved combinatorial tools, including the color-coding technique of Alon, Yuster, and Zwick (1995).