A Top-Down Depth-Four Circuit Lower Bound for Majority
2026-08-10 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors extend previous research that proved limits on how simple certain circuits computing the Parity function can be. They focus on the Majority function, which is harder because changing its output often requires flipping many input bits rather than just one. To tackle this, the authors study inputs with a fixed number of 1s (called slices of the Boolean cube) near half the input size. This approach helps them build a set needed for their proof and show a lower bound on depth-four circuits for Majority.
Majority functionParity functionBoolean cubeHamming weightDepth-four circuitsCircuit lower boundRobust sunflowerMirror setBlock unpredictability
Authors
Hao Wu, Yaqiao Li
Abstract
We present a top-down depth-four circuit lower bound for Majority function by extending recent work of Göös, Riazanov, Sofronova, and Sokolov (FOCS 2023), who gave a top-down proof of a depth-four circuit lower bound for Parity which relies on the robust sunflower to construct a mirror set and the block unpredictability to find the local limits. The main challenge for the case of Majority is to construct a corresponding mirror set, the difference is that to flip the value of Majority function, one may have to flip many bits of the input Boolean string, while for Parity, flipping one bit suffices. We avoid this flipping by considering slices of the Boolean cube, that is, Boolean strings of fixed Hamming weight approximately $n/2$.