Circuit size limits for computing majority clarified after decades
Optimal Shallow Circuits for Majority
Computational Complexity
Summary
People have tried for decades to understand how complex computer circuits need to be to decide if more than half of a list of bits are ones, which is called the Majority function. Earlier, the best known lower limits for circuit complexity were for a simpler function called Parity. The paper presents a new way to build circuits for Majority with sizes matching those theoretical limits exactly. This settles a long-standing question about how efficiently Majority can be computed with shallow circuits.
What this means in practice
- •For circuit designers: Know the minimal size for shallow circuits implementing Majority, guiding optimal hardware designs.
- •For algorithm developers: Understand the limits of parallel algorithms simulating symmetric functions with constant-depth circuits.
A theory result. No direct application yet.
Authors
Victor Lecomte, Prasanna Ramakrishnan
Abstract
Four decades on, Håstad's classical $2^{Ω(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.