The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three".
Jane: Here's the gist of the paper. Optimal monotone depth-three circuit lower bounds for Majority provide an optimal lower bound on the size of monotone depth-3 circuits with bottom fan-in at most 3 computing Majority This result is obtained by solving local enumeration on monotone formulas for k = 3 and all t ≤ n/2.
Tom: Problem Context The paper addresses the problem of finding the largest number of minimum weight satisfying assignments for an n-variate monotone 3-CNF with no satisfying assignment of Hamming weight less than n/2, showing a tight upper bound of 6n/4.
Jane: This problem is closely related to the complexity of Majority function and k-SAT.
Tom: The authors provide an optimal algorithm that solves local enumeration on monotone formulas for k = 3 and all t ≤ n/2.
Paper summary: Tom: To wrap up the "The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three" paper we established that there is an optimal lower bound on the size of monotone depth-three circuits with bottom fan-in three computing Majority.
Jane: That means we have a concrete number for how big these circuits must be, and the authors prove this is tight by showing they can actually build a circuit that reaches that size >
Lu: The implication is that their method, local enumeration on monotone formulas for k equals three and all t less than or equal to n over two, is the right path to settling the depth-three complexity of Majority >
Meng: For deployment purposes, knowing this exact size gives us a hard target for what we should expect when we try to compute Majority function in a constrained hardware setting >
Tom: So it’s not just about saying it's hard; they gave us the exact measure of how hard it is for these specific constraints on depth and fan-in >
Jane: That’s right, and this work helps clarify where the barriers are in circuit complexity, especially when you look at monotone functions like Majority >
Conclusion: Tom: So we've been looking at how big these monotone depth three circuits have to be to compute the Majority function, and this paper lays out a real upper bound for that size.
Jane: It seems like they’ve found the exact number of transistors or gates you need, which is pretty concrete information for anyone trying to build something with these specific limitations.
Lu: What's interesting about their method is that they figured out how to use local enumeration on monotone formulas for k equals three and all t less than or equal to n over two. That’s a very specific way of counting the possibilities.
Meng: So what does this actual size bound mean for us when we're trying to deploy something in the real world? It gives us a hard number to aim for, which is better than just saying it's "hard."
Tom: Exactly. It’s not just theoretical; it tells you the minimum size of these specific circuits. They established this lower bound by showing that any monotone depth three circuit with bottom fan-in three must be at least as big as this number.
Jane: And they prove their result is tight, meaning they've also shown that a circuit of exactly that size can actually compute the Majority function. That closes the gap between what we *think* it's possible and what we *know* it is possible with these rules.
Lu: The proof structure itself, using induction on n and t, analyzing those structural configurations like triangle or path arrangements for the three two-clauses—that shows the depth three constraint really limits the complexity in a predictable way.
Meng: I'm curious about what happens if we step up to four variables or higher with this same circuit structure. Does this exact bound hold up when you move away from just Majority?
Tom: That’s a big question for them, right? They've nailed the three variable case, but extending these specific structural analyses to more variables is the next logical hurdle in their research.
Jane: So, while they've given us the exact measure for this specific setup, it opens up questions about how these bounds change when you introduce more complexity or different function types. We should look into whether this technique scales beyond three variables and what that implies for general computation.
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard
Cornell University · University of California, San Diego
cs.CC
Submitted: 2026-01-07
Updated: 2026-11-10
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 78/100
The gist: Optimal monotone depth-three circuit lower bounds for Majority provide an optimal lower bound on the size of monotone depth-3 circuits with bottom fan-in at most 3 computing Majority This result is…
Key concepts
- Majority Function
- The Majority function outputs '1' if the number of '1' inputs is greater than half the total inputs, and '0' otherwise. The paper investigates how hard it is to compute this function using specific types of logic circuits.
- Monotone Circuit
- A monotone circuit is a computational circuit where every gate only uses the logical AND and OR operations. This means that if you change an input from 0 to 1, the output can only change from 0 to 1, never from 1 to 0.
- Depth-Three Circuit
- Circuit depth refers to the longest path from an input gate to the output gate. A depth-three circuit means that information must pass through at most three layers of gates (e.g., input -> layer 1 -> layer 2 -> output). This constraint is used to derive lower bounds on circuit size.
- Local Enumeration
- This is a technique used in the proof to systematically explore all possible ways a monotone formula can satisfy certain conditions related to the Majority function. It involves enumerating specific structures, like transversals of subformulas, to bound the total number of possible satisfying assignments.
Terminology
Summary
Optimal monotone depth-three circuit lower bounds for Majority provide an optimal lower bound on the size of monotone depth-3 circuits with bottom fan-in at most 3 computing Majority This result is obtained by solving local enumeration on monotone formulas for k = 3 and all t ≤ n/2. p. 0 As the first non-trivial
case, they gave an algorithm for k = 3 which in particular gave a new lower bound on the size
of depth-3 circuits with bottom fan-in at most 3 computing Majority. In this paper, we give
an optimal algorithm that solves local enumeration on monotone formulas for k = 3 and all
t ≤ n/2.Where the paper says it
Problem Context
The paper addresses the problem of finding the largest number of minimum weight satisfying assignments for an n-variate monotone 3-CNF with no satisfying assignment of Hamming weight less than n/2, showing a tight upper bound of 6n/4. This problem is closely related to the complexity of Majority function and k-SAT. p. 1 Our proof in fact gives
a deterministic algorithm that enumerates these solutions. This problem is closely related to the
complexity of Majority function and k-SAT. As the first non-trivial
case, they gave an algorithm for k = 3 which in particular gave a new lower bound on the size
of depth-3 circuits with bottom fan-in at most 3 computing Majority. In this paper, we give
an optimal algorithm that solves local enumeration on monotone formulas for k = 3 and all
t ≤ n/2.Where the paper says it
Where the paper says it
Key Theoretical Background
The paper reviews relevant circuit complexity results, noting that Parity requires depth-d circuits of size 2omega(n(1/(d−1))). Depth-3 circuits are interesting because strong enough lower bounds imply super-linear lower bounds for circuits of logarithmic depth. p. 1 Thus, strong
enough depth-3 lower bounds imply super-linear lower bounds for circuits of logarithmic depth. A
particularly interesting class of depth-3 circuits is Σ
k
3
; Or-And-Or circuits where the bottom gates
have a fan-in of at most k, i. This remains the best known lower bound for computing any explicit
function by Σ
k
3
circuits. The core technique in these lower bounds is a combinatorial result about
the structure of satisfying assignments of k-CNF formulas which can be exploited to solve k-SAT.Where the paper says it
Where the paper says it
Methodology and Main Result
The main result is an optimal lower bound on the size of any monotone Σ3 cubed circuit computing Majority matching upper bounds conjectured in the literature. This is proven by optimally solving Enum+(3, n/2) The optimal algorithm for Enum+(3, t) for t ≤ n/2 is obtained by showing via a constructive argument that extremal monotone 3-CNF consistent with Majority function cannot accept more than 6n/4 transversals of Hamming weight floor(n/2). p. 2 Consequently, Size+3
3
(Majn
) ≥ (2/6
1/4
)
n−o(n) ≃ 1. The optimal algorithm for Enum+(3, t) for t ≤ n/2 is in turn obtained by showing via a
constructive argument that extremal monotone 3-CNF consistent with Majority function (explained
below) cannot accept more than 6
n/4
transversals (satisfying assignments) of Hamming weight ⌊
n
2
⌋.Where the paper says it
Proof Structure
The proof proceeds by induction on n and t, utilizing a top-down technique where the size of a Σk cubed circuit is related to the number of its depth-2 circuits. The proof involves analyzing properties P(i, j) for various types i of monotone 3-CNFs. p. 3 Our approach to the
proof leads to an algorithm to enumerate the transversals. 2 Monotone CNFs and Transversals
A CNF (for Conjunctive Normal Form) formula F = (V, F) is a collection F of clauses (where each
clause is a set of literals) over a set V of Boolean variables. In the other case, our anchor will be A
′ = A ∪ {C} where
C ∈ F is a clause that contains a but not b. Since every t-transversal of F is an extension of some transversal of the anchor, we enumerate
all transversals of the anchor, and for each such transversal we bound the number of extensions
that lead to t-transversals.Where the paper says it
Where the paper says it
Conclusion and Open Questions
The results suggest several open problems, including extending these results for general Σ3 cubed and settling the question regarding the complexity of Majority function for k ≥ 4. It is also noted that it would be interesting to extend the construction for thresholds beyond n/2 even for monotone Σ3 cubed. The paper concludes by presenting a branching algorithm for enumerating the corresponding transversals. p. 9 Algorithmic aspect. It is easy to observe that our proof in fact gives a branching algorithm for
enumerating the corresponding transversals.Where the paper says it
Optimality of Building Blocks
The authors establish optimality by relying on an approach of upper bounds guiding lower bounds where guessing the optimal constructions played an essential role in proving their optimality. The proof relies on inductive structure in the constructions of extremal monotone 3-CNFs for general and restricted 3-CNFs. p. 3 Several
ingredients helped the induction to succeed:
1. Inductive structure in the constructions of extremal monotone 3-CNFs for general and restricted 3-CNFs (for example, 3-CNFs which are required to include a 2-clause),
2. 5 (Transversal number). The transversal number τ (F) of a monotone CNF F is the
cardinality of its minimum-size transversals. The last row contains the sum of the fractions. The induction step is successful if the fractions
add up to a total less than or equal to 1.Where the paper says it
Where the paper says it
Where the paper says it
Detailed Bounds for Configurations
Specific bounds are derived for various types of monotone 3-CNFs based on their structural properties. For example, the bound for Φ4(s, t) is given by Corollary 4. p. 8 Φ1(s, t) ≤
(5
6
(
2
3
)
s
2 3
t
s = 0 mod 2, t ≥ 0, s ≤ 3t
2
3
(
2
3
)
s−1
2 3
t
s = 1 mod 2, t ≥ 0, s ≤ 3t
Monotone 3-CNFs with two 2-clauses which overlap in one variable
Φ2o(s, t) ≤
(
(
2
3
)( 2
3
)
s
2 3
t
s = 0 mod 2, t ≥ 0, s ≤ 3t
5
9
(
2
3
)
s−1
2 3
t
s = 1 mod 2, t ≥ 0, s ≤ 3t
Monotone 3-CNFs with two 2-clauses which are disjoint
Φ2d(s, t) ≤
(
(
5
6
)
2
(
2
3
)
s
2 3
t
s = 0 mod 2, t ≥ 0, s ≤ 3t
5
9
(
2
3
)
s−1
2 3
t
s = 1 mod 2, t ≥ 0, s ≤ 3t
Monotone 3-CNFs with three 2-clauses which do not have an variable in common
Φ3(s, t) ≤
( 7
12 (
2
3
)
s
2 3
t
s = 0 mod 2, t ≥ 0, s ≤ 3t
1
2
(
2
3
)
s−1
2 3
t
s = 1 mod 2, t ≥ 0, s ≤ 3t
Monotone 3-CNFs with four 2-clauses
Φ4(s, t) ≤
( 7
12 (
2
3
)
s
2 3
t
s = 0 mod 2, t ≥ 0, s ≤ 3t
17
36 (
2
3
)
s−1
2 3
t
s = 1 mod 2, t ≥ 0, s ≤ 3t
Recall that we are primarily interested in the number of transversals of size ⌊n/2⌋ in an n-vertex
3-graph with no transversal of smaller size. By setting t = ⌊n/2⌋ and s = t, our bound follows. We apply induction to
get that the ratio of the number of transversals of the restricted formula to Φ0(s, t) is at most 1
12
regardless of the parity of s. The sum of the fractions is at most 1, so our induction is successful. They gave an algorithm
that optimally solves this problem for k = 3. 1 Our contribution
Our main result is an optimal lower bound on the size of any monotone Σ
3
3
circuit computing
Majority matching the upper bounds conjectured in the literature (see e. The induction step is successful if the fractions
add up to a total less than or equal to 1. Core variables Forced variables Restricted CNF parameters Inductive bound
a b n
′
t
′
s
′ Type Even s Odd s
1 b = 0 n − 2 t − 1 s − 1 0
7
18
3
7
0 1 n − 2 t − 1 s − 1 0
7
18
3
7
0 0 c = d = e = 1 n − 5 t − 3 s − 4 0
1
12
1
12
Total 31
36
79
84
Note 4.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Optimal Monotone Depth-Three Circuit Lower Bounds for Majority: The system can establish tight lower bounds on monotone depth-three circuits computing Majority, specifically proving Size33(Majn) >= (2/6 1/4)n, which is approximately 1.277n.
-
Local Enumeration for Monotone Formulas: The AI can solve local enumeration on monotone formulas for k=3 and all t <= n/2 in expected time poly(n) times 6n/4, which directly leads to the lower bound on Size+33(Majn).
-
Utilizing Extremal k-CNFs: The system can identify extremal monotone 3-CNFs consistent with Majority function by using a modularity principle and an inductive approach based on properties P(0, j) to guide the search for optimal constructions.
-
Transversal Enumeration Algorithm: The AI can implement a branching algorithm for enumerating transversals of extremal monotone 3-CNFs, which is used to prove the lower bounds by bounding the number of extensions that lead to t-transversals.
-
Circuit Complexity Analysis via Threshold Functions: The system can relate the size of monotone depth-3 circuits computing t-threshold functions to the number of transversals using Fact 2.11 and Fact 2.12, providing a method to establish upper bounds on circuit sizes based on transversal numbers.
Abstract
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 at most 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.
Sources
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?