Optimal Monotone Depth-Three Circuit Lower Bounds for Majority

Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +3

Gurumuhkani et al. (CCC'24) introduced the local enumeration problem $Enum(k,t)$ as follows: for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no sat…