Local Enumeration and Majority Lower Bounds

Depth-3 circuit lower bounds and k-SAT algorithms are intimately related; the state-of-the-art Σᵏ₃-circuit lower bound and the k-SAT algorithm are based on the same combinatorial theorem. In this paper we define a problem which reveals new interactions between the two. Define Enum(k, t) problem as: given an n-variable k-CNF and an initial assignment α, output all satisfying assignments at Hamming distance t from α, assuming that there are no satisfying assignments of Hamming distance less than t from α. Observe that: an upper bound $b(n, k, t)$ on the complexity of Enum(k, t) implies: - Depth-3 circuits: Any Σᵏ₃ circuit computing the Majority function has size at least nn/2/b(n, k, n/2). - k-SAT: There exists an algorithm solving k-SAT in time O(∑t = 1n/2b(n, k, t)). A simple construction shows that b(n, k, n/2) ≥ 2(1 - O(log(k)/k))n. Thus, matching upper bounds would imply a Σᵏ₃-circuit lower bound of 2Ω(log(k)n/k) and a k-SAT upper bound of 2(1 - Ω(log(k)/k))n. The former yields an unrestricted depth-3 lower bound of 2ω(√n) solving a long standing open problem, and the latter breaks the Super Strong Exponential Time Hypothesis. In this paper, we propose a randomized algorithm for Enum(k, t) and introduce new ideas to analyze it. We demonstrate the power of our ideas by considering the first non-trivial instance of the problem, i.e., Enum($3$, n/2). We show that the expected running time of our algorithm is 1.598ⁿ, substantially improving on the trivial bound of 3n/2 1.732ⁿ. This already improves Σ³₃ lower bounds for Majority function to 1.251ⁿ. The previous bound was 1.154ⁿ which follows from the work of H{}stad, Jukna, and Pudl\'ak (Comput. Complex.'95).