arXiv · Sep 27, 2026
Optimal Shallow Circuits for Majority
By Victor Lecomte, Prasanna Ramakrishnan
Four decades on, H{aa}stad's classical 2^Ω(n^(1/(d-1))) lower bound for depth-d circuits computing Parity remains the best known AC⁰ 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 AC⁰ circuit complexity of Majority, matching H{aa}stad's lower bound. The proof draws inspiration from well-loved combinatorial tools, including the color-coding technique of Alon, Yuster, and Zwick (1995).