OpenAlex ·
Optimal Shallow Circuits for Majority
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.34029
- Original
- Read it at the publisher
- Topics
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. The proof draws inspiration from well-loved combinatorial tools, including the color-coding technique of Alon, Yuster, and Zwick (1995).
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
An EPTAS for Offline Temporary Tasks Assignment on Few Machines
Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective
Depth-Optimal Quantum Compilation
Higher-Order Mean-Field Control Barrier Functions
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.