Local Enumeration and Majority Lower Bounds

Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák +2

Depth-3 circuit lower bounds and $k$-SAT algorithms are intimately related; the state-of-the-art ${\Sigma }_3^k$-circuit lower bound and the $k$-SAT algorithm are based on the same combina…