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, n2). - k-SAT: There exists an algorithm solving k-SAT in time O (ₓ = ₁^n/2b (n, k, t) ). A simple construction shows that b (n, k, n2) 2^ (1 - O ( (k) /k) ) n. Thus, matching upper bounds would imply a ᵏ₃-circuit lower bound of 2^ ( (k) n/k) and a k-SAT upper bound of 2^ (1 - ( (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, n2). We show that the expected running time of our algorithm is 1. 598ⁿ, substantially improving on the trivial bound of 3^n/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 Hstad, Jukna, and Pudl\'ak (Comput. Complex. '95).