The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three
summary
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…
In short
This work establishes an optimal lower bound for monotone depth-three circuits computing Majority, specifically when the bottom fan-in is limited to three. The result proves that any such circuit must have a size of at least 6n/4. This is achieved by optimally solving local enumeration on monotone formulas for k=3 and all t ≤ n/2, providing a tight bound.
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 used across episodes
This episode discusses
- The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three · Paper Radio
- On Extremal Properties of k-CNF: Capturing Threshold Functions
The paper
The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three · Read on arXiv
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard
Cornell University · University of California, San Diego
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.
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.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game