💻 computer science

Optimal Lower Bounds for Symmetric Modular Circuits

This paper resolves a longstanding open problem in circuit complexity by establishing tight subexponential lower bounds for computing the Boolean AND function using symmetric modular circuits, demonstrating that optimal size is achieved at depth 2 and extending these results to circuits with nested block symmetry.

Original authors: Benedikt Pago

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benedikt Pago

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 trying to build a massive, super-secure vault door. This door only opens if every single one of its $n$ keys is turned to the "ON" position. In computer science, this is called the AND function.

For decades, computer scientists have been arguing about the best way to build this door. Specifically, they are asking: Can we build this door using only "Modular Counting" gears?

Think of a Modular Counting gear (a MOD gate) as a special machine that counts how many keys are turned on, but it only cares about the remainder when that number is divided by a specific number (like 6). If the remainder is in a "magic list," it says "Open." Otherwise, it says "Stay Closed."

The big question is: Can we build a door that only opens when all keys are on, using only these remainder-counting gears?

The Problem: The "Symmetry" Trap

For 30 years, no one could prove that you can't do this efficiently. We know the reverse is true (you can't build a remainder counter using simple on/off switches), but the other way around remained a mystery.

The author of this paper, Benedikt Pago, decided to solve a specific, slightly restricted version of this problem. He asked: "What if we force the door to be perfectly symmetrical?"

Imagine the vault door is made of identical gears arranged in a circle. If you rotate the whole door, it looks exactly the same. In math terms, the circuit must treat every input key exactly the same way. If you swap key #1 and key #100, the door's internal logic must just swap those two gears and work exactly the same.

The Big Discovery: "Two Layers is Enough"

Pago's main result is a bit surprising. He proved that if you are forced to keep this perfect symmetry, you cannot build a smaller door just by making it deeper.

The Old Idea: Maybe if we stack 10 layers of these counting gears, we can make the door much smaller and more efficient.
The New Reality: Pago proved that if you are symmetric, a 2-layer door is already the best you can do. Adding more layers (3, 4, or 100) doesn't save you any space. You hit a "wall" of efficiency immediately.

He showed that the smallest possible size for this symmetric door grows at a specific rate (roughly $2^{n^{1/r}}$ ), and a clever 2-layer design already hits that limit. It's like realizing that no matter how many times you fold a piece of paper, you can't make it smaller than a certain size if you have to keep the pattern symmetrical.

The Twist: Breaking the Pattern

But wait, there's a catch. The paper also explores what happens if you break the perfect symmetry.

Imagine the vault door isn't a perfect circle, but a Russian Nesting Doll structure.

You have groups of keys.
Those groups are inside bigger groups.
Those are inside even bigger groups.

This is called "Nested Block Symmetry." It's less strict than the perfect circle. You can treat the keys inside "Group A" differently from "Group B," as long as you treat the keys within Group A symmetrically.

Pago found that if you use this "Nesting Doll" approach, you can build a smaller door by adding more layers.

The Trade-off: You can make the door smaller, but it gets deeper (more layers).
The Sweet Spot: The paper calculates the exact mathematical balance. If you want the smallest door, you should split your keys into equal-sized groups at every level of the nesting.

Why Does This Matter?

This isn't just about vault doors. It's about the fundamental limits of computing.

The "Symmetry" Lesson: It tells us that for certain types of problems, trying to be "fair" to all inputs (symmetry) limits how much we can optimize. Sometimes, to get the best performance, you have to treat inputs differently (break symmetry).
The 30-Year Mystery: This helps solve a 30-year-old puzzle about whether "Modular Counting" circuits (CC0) are powerful enough to do everything "Standard Boolean" circuits (ACC0) can do.
- If we can prove that any efficient circuit for this problem can be turned into a symmetric one, then Pago's proof means Modular Counting is weak and can't do everything.
- If we find a way to build a tiny, efficient door that breaks symmetry, it might mean Modular Counting is actually very powerful.

The Analogy Summary

The Goal: Build a "All-Or-Nothing" switch.
The Tools: Only "Remainder Counters" (gears that count mod 6, mod 7, etc.).
The Constraint: The machine must look the same if you swap any two inputs (Symmetry).
The Result:
- If you keep it perfectly symmetrical, 2 layers is the limit. You can't get smaller by adding depth.
- If you allow a "Nesting Doll" structure (partial symmetry), you can get smaller, but you need more layers.
- The Takeaway: Symmetry is a powerful constraint. It forces you to hit a size limit very quickly, and the most elegant solution (the 2-layer design) is actually the optimal one under those rules.

This paper essentially drew a map showing exactly how big these "symmetric" machines must be, closing a chapter on a long-standing mystery and pointing the way for future discoveries in computer complexity.

1. Problem Statement and Context

The Core Question:
The paper addresses a notorious open problem in circuit complexity: Can the $n$ -ary Boolean AND function ( $AND_n$ ) be computed efficiently (in polynomial size) by constant-depth circuits using only modular counting gates ( $MOD_m$ )?

Context: This is the question of whether the complexity class $CC^0$ (constant depth, modular counting gates) equals $ACC^0$ (which includes Boolean AND/OR/NOT).
Current State: While Håstad's switching lemma proved that Boolean gates cannot efficiently simulate modular counting (exponential lower bounds for $MOD_m$ in $AC^0$ ), the reverse direction (simulating Boolean AND with $MOD_m$ gates) remains open. The best known lower bounds for general $CC^0$ circuits are only slightly superlinear.
The Gap: It is conjectured (Exponential Size Hypothesis) that computing $AND_n$ requires size $2^{\Omega(n^\epsilon)}$ for any constant depth $h$ and modulus $m$ with at least two distinct prime factors. However, proving this for general circuits has been elusive for 30 years.

The Approach:
The author restricts the problem to Symmetric Circuits. Since $AND_n$ is symmetric under all permutations of its inputs, it admits symmetric circuit representations. The paper investigates whether imposing symmetry constraints allows for a complete characterization of the circuit complexity, potentially bypassing the difficulties of the general case.

2. Methodology and Technical Framework

The paper employs a group-theoretic approach based on the concept of supports and periodicity.

A. Symmetry Models

The paper analyzes two models of symmetry:

Fully Symmetric ( $Sym_n$ -symmetric): The circuit is invariant under any permutation of the $n$ input variables.
Nested Block Symmetric ( $Aut(T^k_n)$ -symmetric): A relaxed symmetry where the circuit respects a hierarchical "divide-and-conquer" structure defined by a tree $T^k_n$ . The symmetry group is the automorphism group of this tree, which is smaller than $Sym_n$ .

B. The Support Technique

The core technical tool is the notion of a support for a gate in a symmetric circuit.

For a gate $g$ , its stabilizer group $Stab(g)$ (permutations that fix $g$ ) is analyzed.
If the circuit size is small, the minimal support of $Stab(g)$ must be small.
The function computed by a gate with a small support depends only on a small subset of variables and the count of 1s in the remaining variables.

C. Periodicity Argument

The proof strategy relies on showing that small-support symmetric circuits compute periodic functions.

Theorem: If a symmetric $MOD_m$ circuit has small supports (bounded by $s(n)$ ), the function it computes is periodic with a period length related to the prime factors of $m$ and the support size.
Contradiction: The $AND_n$ function is aperiodic (it does not repeat values in a regular pattern relative to the number of 1s).
Conclusion: To compute $AND_n$ , the supports must be large enough to break this periodicity. This forces the circuit size to be large.

3. Key Contributions and Results

Result 1: Optimal Lower Bounds for Fully Symmetric Circuits

Theorem 1.1: For a modulus $m$ with $r \ge 2$ distinct prime divisors, any family of $Sym_n$ -symmetric $MOD_m$ circuits computing $AND_n$ must have size:
$|C_n| \ge 2^{\Omega(n^{1/r} \log n)}$

Significance: This matches the upper bound construction by Idziak et al. (LICS'22).
Surprising Insight: The optimal size is achieved at depth 2. Increasing the depth beyond 2 provides no asymptotic size savings for fully symmetric circuits. This refutes the intuition that deeper circuits might be more efficient under symmetry constraints.

Result 2: Tight Bounds for Nested Block Symmetry

Theorem 1.2: For circuits respecting a nested block symmetry defined by a tree with block sizes $k_1, \dots, k_h$ (where $\prod k_i = n$ ), the size lower bound is:
$|C_n| \ge 2^{\Omega(k_{max}(n)^{1/r} \log k_{max}(n))}$
where $k_{max}(n)$ is the largest block size in the hierarchy.

Implication: The complexity is controlled by the largest block size. To minimize size, one should balance the block sizes ( $k_i = n^{1/h}$ ), yielding a size of $2^{\Theta(n^{1/(h \cdot r)} \log n)}$ .
Depth vs. Size Trade-off: While previous work (Idziak et al.) showed that depth $h+1$ circuits could be smaller than depth $2h$ circuits, those constructions were slightly suboptimal in size compared to the theoretical lower bound derived here.

Result 3: Upper Bounds

The paper confirms that the lower bounds are tight by presenting matching upper bound constructions:

Depth 2: A recursive application of the depth-2 construction from Idziak et al. achieves the bound for fully symmetric circuits.
Depth 2h: A naive recursive construction (applying the depth-2 block construction at each level of the symmetry tree) achieves the bound for nested block symmetry.

4. Significance and Implications

Resolution of the Symmetric Case: The paper completely settles the circuit complexity of $AND_n$ for symmetric circuits. It proves that the Exponential Size Hypothesis (ESH) holds true for these restricted models.
Depth Optimality: It establishes that for fully symmetric circuits, depth 2 is optimal. One cannot trade depth for size in this model; breaking symmetry is the only way to potentially gain size efficiency.
Methodological Advance: The extension of support-based lower bound techniques to nested block symmetries (automorphism groups of trees) is a significant technical contribution. It moves beyond the standard symmetric group $Sym_n$ to more complex, hierarchical symmetry groups.
Path to General Lower Bounds: The paper poses a critical open question: Can every general $CC^0$ $C C^{0}$ circuit be "symmetrized" with only a small cost in size?
- If Yes: The lower bounds in this paper apply to all $CC^0$ circuits, separating $CC^0$ from $ACC^0$ .
- If No: It implies that breaking symmetry is essential for efficient modular circuits, and finding such non-symmetric constructions would be a major breakthrough toward proving $CC^0 = ACC^0$ .

Summary

Benedikt Pago's paper provides a definitive answer to the complexity of computing Boolean AND using modular gates under symmetry constraints. By leveraging group-theoretic supports and periodicity arguments, the author proves that symmetric circuits require exponential size (specifically $2^{\Omega(n^{1/r} \log n)}$ ) and that this bound is tight even at depth 2. This work not only solves a specific open problem in circuit complexity but also provides a rigorous framework and new open questions that could guide the resolution of the broader $CC^0$ vs. $ACC^0$ problem.