💻 computer science

ETH-Hardness of Learning Monotone Circuits and Approximating Their Size

This paper establishes that, under the Randomised Exponential-Time Hypothesis, learning monotone formulas and approximating the size of monotone circuits are computationally hard problems requiring super-polynomial time, a result achieved by applying novel lifting arguments from proof and communication complexity to extend the hardness of automating Resolution proofs.

Original authors: Bruno Cavalar, Susanna F. de Rezende, Matthew Gray, Rahul Santhanam

Published 2026-07-15

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Bruno Cavalar, Susanna F. de Rezende, Matthew Gray, Rahul Santhanam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but the clues are hidden inside a giant, tangled ball of string. Your job is to find the shortest, simplest way to untangle it. In the world of computer science, this "string" is a monotone circuit—a specific type of logic machine that can only say "yes" or "no" based on inputs, but it's forbidden from using a "NOT" switch (it can't say "no" to a "no").

The paper you're reading is a team of researchers (Bruno, Susanna, Matthew, and Rahul) who just dropped a massive bombshell on the idea that we can easily learn how to build these machines or guess their size. They didn't just find a hard puzzle; they proved that under a very famous assumption called the Randomised Exponential-Time Hypothesis (rETH), solving these puzzles is so incredibly difficult that it might as well be impossible for any computer we can build today.

Here is the story of what they found, told without the heavy math jargon.

The Great "Untangle" Challenge

Think of a monotone formula as a simple, straight-line recipe. It's easy to follow, but it can only do so much. Now, think of a monotone circuit as a complex, branching factory with many shortcuts and loops. It's much more powerful.

The researchers asked a simple question: If I give you a bunch of examples of how a simple recipe works, can you quickly figure out how to build a complex factory that does the same thing? Or, if I give you a messy list of inputs and outputs, can you quickly guess the smallest factory needed to produce them?

The answer, according to this paper, is a resounding "No, not quickly."

The Magic Trick: The "Refuter" Game

To prove this, the authors didn't just guess; they built a clever trap. They used a technique called lifting, which is like taking a small, simple puzzle and stretching it out into a giant, confusing maze that looks like a completely different problem.

They started with a classic logic game called Resolution. Imagine a game where two players, a "Prover" and an "Adversary," are trying to prove a statement is impossible.

If the statement is possible (satisfiable), the Prover can find a way to untangle the logic very quickly, using a shallow, simple path.
If the statement is impossible (unsatisfiable), the Prover gets stuck in a deep, wide, and incredibly complex maze.

The authors created a special formula, which they call Ref*(F). This formula is the "trap."

When the original problem is easy, Ref*(F) is a tiny, shallow puzzle that a simple monotone formula can solve.
When the original problem is hard, Ref*(F) explodes into a massive, wide monster that requires a gigantic monotone circuit to solve.

The genius of their trap is that they made the "easy" version so small (a "junta," or a function that only cares about a few inputs) and the "hard" version so huge that the gap between them is massive. It's like the difference between a paperclip and a skyscraper.

The Big Findings: Why You Can't Cheat

Using this trap, the team proved two main things, assuming the rETH (which basically says that some logic puzzles, like 3SAT, simply cannot be solved faster than a certain exponential speed limit):

1. You can't learn these circuits quickly.
If you try to teach a computer to learn a simple monotone formula (the paperclip) by letting it guess using a slightly larger monotone circuit (a small factory), the computer will take forever.

The Time: To learn a formula of size n (where n is the number of inputs), a computer would need nΩ(log n) time.
What this means: If n is 100, the time isn't just a bit longer; it's so long that it grows faster than any polynomial (like n² or n¹⁰⁰). It's a "quasipolynomial" nightmare. Even if you let the computer use a circuit that is slightly bigger than the formula it's trying to learn, it still hits a wall.

2. You can't even guess the size of the circuit.
Imagine someone hands you a list of 100 examples (like "Input A gives Output 1, Input B gives Output 0") and asks, "What is the smallest factory needed to make these?"

The paper proves that if you want to guess the size of this factory within a factor of m¹⁻δ (where m is the number of examples), you will also need mΩ(log m) time.
The Catch: This isn't just a "maybe." The paper shows that distinguishing between a case where the factory is tiny and a case where it's huge is so hard that no algorithm running in No(log N) time can do it. Here, N is the total size of the input data.

What This Rules Out

The paper is very clear about what it does not do, and what it rules out:

It does not say that learning is impossible forever. It says it's impossible quickly under the rETH assumption. If rETH is false (and we find a magic way to solve 3SAT super fast), then these results might vanish.
It does not prove that learning is NP-hard in the traditional sense (which would be a huge, world-shattering proof). Instead, it proves a "quasipolynomial" lower bound. This is a strong "no," but it's a specific kind of "no" that fits within the current understanding of fine-grained complexity.
It explicitly rules out the idea that we can easily approximate the size of these circuits. You can't just get "close enough" quickly. The gap between the easy case and the hard case is too wide to bridge with a quick guess.

How Sure Are They?

The authors are very confident, but they are also honest about their assumptions.

The Proof: They have a rigorous mathematical proof. They didn't just run a simulation or suggest an idea; they built a logical reduction.
The Assumption: Their entire result rests on the Randomised Exponential-Time Hypothesis (rETH). This is a standard, widely accepted belief in the computer science community, but it hasn't been proven true yet. It's like saying, "Assuming gravity works the way we think it does, this bridge will collapse." If gravity changes, the bridge might stand. But as long as we believe in rETH, the bridge is definitely collapsing.

The Takeaway for the Curious Teen

Imagine you are trying to teach a robot to recognize a specific pattern. You give it a few examples. The robot tries to build a machine to recognize the pattern.

Old belief: Maybe the robot can figure it out pretty fast, even if it's not perfect.
This paper's discovery: If the pattern is a "monotone" one (no "NOT" switches allowed), and you want the robot to be even slightly better than random guessing, it's going to take the robot longer than the age of the universe to figure it out, unless the fundamental rules of logic (rETH) are wrong.

The authors didn't just find a hard problem; they showed that the difficulty of learning these circuits is deeply connected to the difficulty of proving logic statements. It's a beautiful, terrifying link between "learning" and "proving." They used the tools of proof complexity (how hard it is to prove a math theorem) to build a wall that learning algorithms cannot climb.

So, the next time someone tells you that "AI can learn anything quickly," remember this paper. For a specific, important class of logic machines, the universe seems to have put up a "Do Not Disturb" sign that says: "This will take nΩ(log n) time. Good luck."

Technical Summary: ETH-Hardness of Learning Monotone Circuits and Approximating Their Size

Problem Statement

This paper addresses two interconnected challenges in theoretical computer science: the hardness of learning monotone Boolean functions and the hardness of approximating the size of monotone circuits. Specifically, the authors investigate:

Monotone Learning: The difficulty of PAC-learning monotone formulas (concept class) using monotone circuits (hypothesis class) under worst-case complexity assumptions, rather than cryptographic assumptions.
Monotone Circuit Size Approximation: The difficulty of distinguishing between monotone functions that can be computed by small monotone formulas and those that require significantly larger monotone circuits, given only a sequence of labeled examples (the Partial Minimum Monotone Circuit Size Problem).

The authors aim to establish strong inapproximability results and learning lower bounds based on the Randomized Exponential-Time Hypothesis (rETH), avoiding the limitations of previous work that relied on cryptographic assumptions or yielded only weak approximation gaps.

Methodology

The core technical contribution is a novel application of lifting arguments from proof complexity and communication complexity to the domain of learning and circuit size approximation. The methodology proceeds through the following steps:

1. Automating Resolution and Refutation Formulas

The authors build upon the seminal result of Atserias and Müller [AM20], which established that automating Resolution proofs is hard. They construct a specific family of formulas, denoted $\text{Ref}^*_G(F)$ , derived from a 3-CNF formula $F$ .

Construction: Unlike previous constructions that focused on Resolution size gaps, the authors design $\text{Ref}^*_G(F)$ to exhibit a gap in Resolution depth (for satisfiable $F$ ) versus Resolution width (for unsatisfiable $F$ ).
Key Innovation: They introduce a new formula structure using "summary variables" (encoding the absence of literals) and "pointer variables" organized via bipartite expander graphs. This allows them to refute the formula in shallow depth ( $O(\sqrt{n})$ ) when $F$ is satisfiable, while requiring exponential width ( $2^{\Omega(\sqrt{n})}$ ) when $F$ is unsatisfiable.
Trade-off: This construction involves a careful trade-off: increasing the size of the formula to $2^{O(\sqrt{n})}$ to achieve a reduction in Resolution depth and width parameters.

2. Lifting to Monotone Complexity

The authors apply a DAG-like lifting theorem (specifically from [dRV25]) to the constructed formula $\text{Ref}^*_G(F)$ .

The Lifting Process: The formula is composed with an "index gadget" to create a partial Boolean function $f_{F,m}$ .
Complexity Connection: The lifting theorem translates the Resolution depth/width properties of $\text{Ref}^*_G(F)$ $Ref_{G}^{*} (F)$ into monotone circuit/formula size bounds for $f_{F,m}$ $f_{F, m}$ .
- If $F$ is satisfiable, $f_{F,m}$ has a small monotone formula size (related to the shallow depth of the refutation).
- If $F$ is unsatisfiable, any monotone circuit approximating $f_{F,m}$ must have super-polynomial size (related to the large width of the refutation).
Distributional Gap: The authors define a distribution $D$ over labeled examples derived from $f_{F,m}$ . In the "easy" case, a small formula perfectly fits the distribution. In the "hard" case, no small circuit can fit the distribution better than random guessing (with a specific error margin).

3. Reduction to Learning and Approximation

The authors reduce the 3SAT problem to a Monotone Circuit-Formula Gap Learning (mCFGL) problem.

Gap Learning: The task is to distinguish whether a distribution is consistent with a small monotone formula or inconsistent with any small monotone circuit.
Sampling: They show that solving the Partial-Monotone-MCSP (given a sequence of examples) or PAC-learning the concept class is at least as hard as solving this gap learning problem. By sampling sufficiently many examples from the distribution $D$ , they ensure that any small circuit will fail to approximate the target function with high probability in the hard case.

Key Contributions and Results

1. Hardness of PAC-Learning Monotone Formulas

Under the Randomized Exponential-Time Hypothesis (rETH), the authors prove that learning monotone formulas is hard even when the hypothesis class is allowed to be larger than the concept class (semi-proper learning).

Result: For every $\epsilon > 0$ , PAC-learning monotone formulas of size $n$ (on $n$ inputs) using monotone circuits of size $n(\log n)^{1-\epsilon}$ requires time $n^{\Omega(\log n)}$ .
Significance: This is the first strong hardness result for learning monotone circuits under worst-case assumptions. Previous results relied on cryptographic assumptions or were limited to proper learning of weak classes.

2. Strong Inapproximability of Monotone Circuit Size

The paper establishes strong inapproximability for the Partial Minimum Monotone Circuit Size Problem.

Result: Under rETH, for any constant $c > 1$ , there is no algorithm running in time $N^{o(\log N)}$ that can distinguish between a set of labeled examples consistent with a monotone formula of size $n$ and a set of examples inconsistent with any monotone circuit of size $n^c$ .
Approximation Gap: Consequently, there is no $N^{1-\epsilon}$ -multiplicative approximation algorithm for partial monotone formula or circuit size running in $N^{o(\log N)}$ time.
Comparison: This improves upon previous work (e.g., [Hir22]) which only achieved sublinear gaps between program sizes or relied on weaker assumptions. The authors achieve a super-polynomial gap between formula size and circuit size.

3. Parameterized Trade-offs

The authors demonstrate a trade-off between the size of the concept class (formulas) and the hypothesis class (circuits), yielding different runtime lower bounds:

Junta vs. Quasipolynomial: Learning small "junta" formulas by quasipolynomial circuits requires $N^{\Omega(\log \log N)}$ time.
Linear vs. Polynomial: Learning linear-size formulas by polynomial-size circuits ( $n^c$ ) requires $N^{\Omega(\log N)}$ time.

Significance and Claims

The paper claims to provide a new pathway for establishing hardness in meta-complexity and learning theory by leveraging the connection between automatability of proof systems and learning.

Bridging Fields: The work explicitly connects the hardness of automating Resolution proofs (a proof complexity result) to the hardness of learning and approximating circuit sizes. This validates the connection between learning and proof automatability proposed in earlier works [ABF+08].
Worst-Case Assumptions: By relying on rETH rather than cryptographic assumptions, the results offer a more robust understanding of the inherent difficulty of these problems in the worst-case setting.
Strong Inapproximability: The authors argue that their results are significant because they provide strong inapproximability (super-polynomial gaps) for monotone circuit size, a measure that has been under-studied despite its central role in complexity theory. They note that showing NP-hardness for the Minimum Monotone Circuit Size Problem is a significant step toward the Minimum Circuit Size Problem (MCSP).
Limitations: The authors modestly note that their techniques currently yield a trade-off where they can show hardness for learning formulas of slightly super-polylogarithmic size by polynomial-size circuits, but the full hardness of learning general monotone circuits remains an open challenge under standard worst-case assumptions.

In summary, the paper demonstrates that the difficulty of automating Resolution proofs can be "lifted" to prove that learning monotone formulas and approximating monotone circuit sizes are computationally intractable under the rETH, providing the first strong inapproximability results for monotone circuit size under worst-case assumptions.