← 研踪 PaperTrailarXiv:2601.04072 · v3
The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three
首次提交 2026-01-08 00:38
版本更新 2026-11-10 19:15
雷达观测 2026-11-11 13:08
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-10 19:15 · 最新观测版本
The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three
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.
查看此版本解读 →查看此版本原文 ↗