The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three

arXiv:2601.04072 · cs.CC · Submitted 2026-01-07 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

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.

The authors provide an optimal algorithm that solves local enumeration on monotone formulas for k = 3 and all t ≤ n/2. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

The core technique in established depth-3 lower bounds is a combinatorial result about the structure of satisfying assignments of k-CNF formulas. p. 1
Where the paper says it

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.

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

Where the paper says it

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 ⌋.

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

Where the paper says it

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.

For instance, the inductive step involves enumerating transversals of an anchor subformula and bounding the number of extensions that lead to t-transversals. p. 8
Where the paper says it

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.

The analysis details various cases based on the parity of s and structural configurations like triangle or path configurations for the three 2-clauses.

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

Where the paper says it

Algorithmic aspect. It is easy to observe that our proof in fact gives a branching algorithm for enumerating the corresponding transversals.

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

Where the paper says it

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.

The analysis of configurations such as the triangle configuration and the existence configuration is crucial for bounding the number of transversals. p. 4
Where the paper says it

5 (Transversal number). The transversal number τ (F) of a monotone CNF F is the cardinality of its minimum-size transversals.

The proof structure involves a table summarizing the inductive step where fractions must sum to a total less than or equal to 1. p. 9
Where the paper says it

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.

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

Where the paper says it

Φ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.

2: Θ(n, floor(n/2), 3) ≤ 6n/4. The analysis of P(3-ie, i) for even s shows that the number of transversals is bounded by specific fractions depending on the configuration. p. 9
Where the paper says it

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.

This detailed case analysis confirms the tightness of the conjectured upper bounds. p. 2
Where the paper says it

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 final bound derived from P(3-ie, 6) yields a total ratio of 283/288. p. 9
Where the paper says it

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.

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

  1. 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.

  2. 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).

  3. 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.

  4. 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.

  5. 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