Optimal Monotone Depth-Three Circuit Lower Bounds for Majority

Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard · 2026

Read Optimal Monotone Depth-Three Circuit Lower Bounds for Majority by Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04072.txt.

Description

Mohit Gurumukhani leads five co-authors on a problem about listing satisfying assignments of a restricted formula. Local enumeration asks for all assignments with an exact Hamming weight, given that none lighter can satisfy the formula. Earlier work linked fast enumeration to new SAT methods and to circuit lower bounds for Majority.

Gurumukhani and his five co-authors give an optimal algorithm for the monotone case with clause size three, for all weights up to half the variables. As a direct payoff, they obtain an optimal lower bound on the size of monotone depth-three circuits with small bottom fan-in that compute Majority. Optimal here means the bound cannot be improved within that circuit class, which closes the case they study.

Catalog record

CREATORMohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-04072

Browse the full library · About the Tower of Babel