The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard
原文摘要
Lecomte and Ramakrishnan (arXiv'26) recently presented a depth-three circuit of size $2^{O(\sqrt{n})}$ that computes the Majority function, refuting a long held conjecture. Nevertheless, as a fundamental computational primitive which ubiquitously appears across computer science, determining the exact complexity of Majority down to the constant in the exponent, remains important. Gurumukhani et al. (CCC'24) initiated the study of optimal $Σ^k_3$ circuits computing the Majority function. In this work, we determine the exact $Σ^3_3$ complexity of Majority up to polynomial factors. We show that for any $t \le n/2$, given an $n$-variate $t$-threshold 3-CNF, i.e., with no satisfying assignment with Hamming weight less than $t$, the number of weight-$t$ satisfying assignments is at most $2^t(3/2)^{(n-t)/2}$. Along with a matching construction for $t = n/2$, the result implies that the size of the smallest $Σ^3_3$ circuit computing Majority is exactly $poly(n)(2/6^{1/4})^n$. The proof involves two main ingredients: - Reduction to monotone: We formulate a linear program (LP) which is defined only with respect to the monotone part of the formula. We show that bounding the cost function of this LP implies our desired upper bound on the number of minimum weight solutions of the general formula. - Structure of extremal formulas: To bound the cost function of the LP, we develop an extensive inductive argument. The inductive steps are determined by a close inspection of the local structure of extremal formulas with respect to minimum weight. Our result has a natural hypergraph interpretation: it bounds the number of independent sets of size $n-t$ under the condition that the independence number is $n-t$. This is a generalized hypergraph Turán problem and coincides with the classical hypergraph Turán problem at threshold $t=n-k$ for $k$-uniform hypergraphs.
cs.CC