On $CC^0$ Lower Bounds for AND via Torus Polynomials

Jayalal Sarma; Vaibhav Krishan

Symmetric CC° circuits need superpolynomial size to compute AND, via torus-polynomial degree lower bounds.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-15 09:26 UTC pith:CI5GXWVJ

load-bearing objection Abstract-only: new size lower bound for symmetric CC^0 computing AND via a symmetry-preserving torus-polynomial transfer; central transfer cannot be checked yet. the 2 major comments →

arxiv 2607.10236 v2 pith:CI5GXWVJ submitted 2026-07-11 cs.CC

On CC⁰ Lower Bounds for AND via Torus Polynomials

Vaibhav Krishan , Jayalal Sarma This is my paper

classification cs.CC MSC 68Q0668Q17

keywords CC0 circuitsAND functiontorus polynomialssymmetric circuitsdegree lower boundsconstant-degree hypothesismodular gatescircuit complexity

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper takes a long-standing open question—whether the AND function can be computed by constant-depth polynomial-size circuits made only of modular gates (CC°)—and shows that any such circuit that is also symmetric must be exponentially large. The route is approximation by torus polynomials: the authors build, from any depth-h symmetric CC° circuit, a matching-degree symmetric torus polynomial that approximates it, then invoke already-known degree lower bounds for any such polynomial that approximates AND. The resulting size bound is 2 to the power of roughly n raised to 1 over O(h). The same construction yields lower bounds under weaker symmetry notions, and the paper further shows that better degree lower bounds for ordinary (non-symmetric) torus polynomials would give size lower bounds for certain depth-3 modular circuits whose modulus is a product of two primes, thereby advancing the classical constant-degree hypothesis.

Core claim

Any depth-h symmetric CC° circuit computing AND must have size 2^{Ω̃(n^{1/O(h)})}, obtained by constructing a symmetric torus polynomial that approximates the circuit and transferring known degree lower bounds for symmetric torus polynomials that approximate AND.

What carries the argument

An explicit construction that turns a symmetric CC° circuit into a symmetric torus polynomial whose degree is controlled by the circuit’s size and depth, establishing a direct correspondence between the symmetry of the circuit and the symmetry of the polynomial.

Load-bearing premise

That every symmetric CC° circuit admits a symmetric torus-polynomial approximation whose degree is controlled tightly enough by size and depth for existing degree lower bounds on AND to transfer directly into a circuit-size lower bound.

What would settle it

Exhibit a family of depth-h symmetric CC° circuits of size 2^{o(n^{1/O(h)})} that compute AND on n bits, or show that no degree-controlled symmetric torus polynomial can approximate those circuits.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Symmetric CC° circuits of any fixed depth cannot compute AND in polynomial size.
The same size lower bounds hold under weaker notions of circuit symmetry that the construction also covers.
Improved asymmetric torus-polynomial degree lower bounds for AND would yield size lower bounds for MOD_p ∘ MOD_m ∘ AND_{O(1)} circuits when m is semiprime, advancing the constant-degree hypothesis.
The torus-polynomial method is shown to be usable for pure modular circuits (CC°), not only for ACC°.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The degree-control correspondence may be the reusable ingredient for other modular-circuit classes once matching degree lower bounds exist.
If the same correspondence can be made to work without symmetry, the long-standing CC°-versus-AND question would be resolved for unrestricted circuits as well.
The independent Pago lower bounds (via different techniques) suggest the size bound itself is robust even if the torus route later needs repair.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Abstract-only: new size lower bound for symmetric CC^0 computing AND via a symmetry-preserving torus-polynomial transfer; central transfer cannot be checked yet.

read the letter

The one thing to know: this paper claims an exponential size lower bound for depth-h symmetric CC^0 circuits computing AND, of the form 2^{Ω̃(n^{1/O(h)})}, by building a symmetric torus polynomial that approximates the circuit and then invoking Krishan–Vishwanathan degree lower bounds. That is the actual new result relative to the cited literature. Concurrent independent work by Pago (ICALP 2026) gets related lower bounds by different methods, which the abstract discloses cleanly.

What they do well on the page we have: the logical outline is standard and coherent (degree lower bound + approximation construction ⇒ size lower bound). They also give degree upper bounds for a restricted asymmetric class MOD_p ∘ MOD_m ∘ AND_O(1) with m semiprime, and argue that better asymmetric torus-polynomial lower bounds would push on the constant-degree hypothesis. The self-citation of Krishan–Vishwanathan is used as a black box, not a circular derivation; the contribution here is the circuit-to-polynomial transfer and the size bound that follows.

The soft spot is real and load-bearing, but it is an availability problem, not a demonstrated error. The key claim is an “explicit correspondence between the symmetry of the circuit and that of the polynomial.” Without the definition of circuit symmetry, the approximation error, or the degree-control argument, we cannot verify that the quantitative parameters survive the transfer. Any gap in error accumulation or in what “symmetric” means for circuits would break the exponential size bound. The stress-test note is right about that; it is not manufacturing a flaw, it is naming the step we cannot inspect. Everything else (novelty relative to prior work, concurrent disclosure, conditional path for the constant-degree hypothesis) looks fine on the abstract.

Who this is for: people working on ACC^0 / CC^0 lower bounds and torus polynomials. A serious referee should see the full proofs of the transfer theorem and the weaker-symmetry extensions. I would not desk-reject on the abstract alone; the result is important enough within the area and the outline is plausible enough to deserve referee time. Bring it to reading group only after the full text is out and the transfer can be checked. Until then I would not cite it, but I would watch for the camera-ready or journal version.

Referee Report

2 major / 3 minor

Summary. The manuscript proposes a torus-polynomial approach to the question of whether AND lies in CC^0. Invoking degree lower bounds for symmetric torus polynomials approximating AND (Krishan–Vishwanathan, ITCS 2026), it claims that every depth-h symmetric CC^0 circuit computing AND has size 2^{Ω̃(n^{1/O(h)})}. The stated key step is an explicit construction of a symmetric torus polynomial that approximates a given symmetric CC^0 circuit, transferring circuit symmetry into polynomial symmetry so that the known degree bounds apply. Weaker notions of circuit symmetry are also treated. Independently, Pago (ICALP 2026) obtained related lower bounds by different methods. In the asymmetric setting the paper gives degree upper bounds for depth-three circuits MOD_p ∘ MOD_m ∘ AND_{O(1)} when m is semiprime, and argues that stronger asymmetric torus-polynomial lower bounds would advance the constant-degree hypothesis of Barrington–Straubing–Thérien.

Significance. A verified exponential size lower bound for symmetric CC^0 circuits computing AND would constitute concrete progress on a long-standing open question and would demonstrate that torus-polynomial techniques can be made to speak about modular circuits. The claimed symmetry-preserving approximation, if quantitatively tight, would be a reusable technical bridge between circuit classes and polynomial degree bounds. Disclosure of concurrent independent work by Pago is appropriate. The asymmetric upper-bound discussion, if correct, clarifies a concrete special case of the constant-degree hypothesis. All of these contributions remain conditional on the soundness of the unexamined construction and error analysis.

major comments (2)

[Abstract (symmetric size lower bound)] The central size lower bound rests on a single transfer: every symmetric CC^0 circuit of size s and depth h is approximated by a symmetric torus polynomial whose degree is a controlled function of s and h, so that Krishan–Vishwanathan degree lower bounds convert directly into the stated 2^{Ω̃(n^{1/O(h)})} bound. The abstract asserts an “explicit correspondence between the symmetry of the circuit and that of the polynomial” but supplies neither the definition of circuit symmetry, the approximation error, nor the degree-control argument. Any gap in error accumulation across depth, or any mismatch between the circuit’s symmetry group and the polynomial’s symmetry, would invalidate the quantitative claim. This step is load-bearing and cannot be verified from the abstract alone.
[Abstract (asymmetric regime / constant-degree hypothesis)] The degree upper bounds claimed for MOD_p ∘ MOD_m ∘ AND_{O(1)} (m = pq semiprime) are stated without quantitative parameters, error terms, or a proof outline. The subsequent claim that improved asymmetric torus-polynomial lower bounds would yield size lower bounds for semiprime m (and hence progress on the constant-degree hypothesis) depends on an unspecified degree-to-size conversion. Without those details the implication cannot be checked and remains only a plausible outline.

minor comments (3)

[Abstract] The abstract uses both “CC^0” and “symmetric CC^0” without a one-line definition of the symmetry notion employed; a brief parenthetical clarification would help readers unfamiliar with the concurrent literature.
[Abstract] The concurrent independent result of Pago (ICALP 2026) is mentioned only in a single sentence; a short comparison of techniques (even one clause) would orient the reader.
[Abstract] Notation for the soft-O in the exponent (Ω̃) appears without expansion; writing the precise polylog factors once would remove ambiguity.

Circularity Check

0 steps flagged

Self-citation of Krishan–Vishwanathan degree bounds is load-bearing but not circular; the paper’s contribution is the independent circuit-to-polynomial transfer.

full rationale

Only the abstract is available. The claimed size lower bound for depth-h symmetric CC^0 circuits computing AND is obtained by constructing a symmetric torus-polynomial approximation of the circuit and then invoking the degree lower bounds of Krishan & Vishwanathan (ITCS 2026). The first author of that prior work overlaps with the present paper, so the citation is self-citation. However, the abstract presents the prior result as an external black-box degree lower bound and identifies the present contribution as the explicit symmetry-preserving construction that transfers those degree bounds into circuit-size bounds. No equation, definition, or fitted parameter appears in the abstract that would make the size bound equivalent to its inputs by construction. Concurrent independent work by Pago is disclosed. Under the hard rules, ordinary self-citation of a prior technical result used as a black box does not constitute circularity when the present paper supplies an independent transfer argument; the score is therefore 2 (minor self-citation that is not definitionally circular). Full-text verification of the construction would be needed to raise or lower the score further, but the abstract alone supplies no evidence of self-definitional reduction, fitted-input-as-prediction, uniqueness-import, or ansatz-smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

Theory paper whose central size lower bound rests on (i) prior degree lower bounds for symmetric torus polynomials and (ii) a new but un-audited construction that maps symmetric CC^0 circuits to such polynomials. No numeric free parameters are fitted. Background axioms are standard circuit-complexity and approximation-theory assumptions; the symmetry-transfer construction is the main paper-specific ingredient.

axioms (3)

domain assumption Degree lower bounds for symmetric torus polynomials approximating AND (Krishan–Vishwanathan, ITCS 2026) hold as stated and apply to the polynomials produced by the paper’s construction.
Invoked as the black-box engine that converts the new circuit-to-polynomial map into a size lower bound.
ad hoc to paper A symmetric CC^0 circuit of size s and depth h can be approximated by a symmetric torus polynomial whose degree is a controlled function of s and h.
Stated as the key technical ingredient; without this correspondence the size lower bound does not follow.
standard math Standard definitions of CC^0, MOD_m gates, torus polynomials, and circuit symmetry.
Background notions assumed throughout the abstract.

pith-pipeline@v1.1.0-grok45 · 6303 in / 2219 out tokens · 23406 ms · 2026-07-15T09:26:49.710417+00:00 · methodology

0 comments

read the original abstract

We explore a torus polynomial approximation based approach towards a long-standing question: whether $AND$ can be computed by $CC^0$ circuits - the class of constant-depth polynomial size circuits containing $MOD_m$ gates for some $m$. Bhrushundi et al. (ITCS 2019) introduced torus polynomial approximations as an approach for proving lower bounds against $ACC^0$ - a class containing $CC^0$ with circuits comprising $AND$, $OR$ and $NOT$ gates. We show how lower bounds for torus polynomials approximating $AND$ can be used to make progress on this question. Using lower bounds on the degree of symmetric torus polynomials approximating $AND$ from Krishan and Vishwanathan (ITCS 2026), we prove size lower bounds for symmetric $CC^0$-circuits computing $AND$. More precisely, we prove that any depth $h$ symmetric $CC^0$ circuit requires $2^{\widetilde{\Omega}(n^{1/O(h)})}$ size to compute $AND$. A key ingredient in our proof is an argument that we can construct symmetric torus polynomials to approximate symmetric $CC^0$ circuits. Our construction exhibits an explicit correspondence between the symmetry of the circuit and that of the polynomial. Using this, we also establish lower bounds for weaker notions of circuit symmetry. Lower bounds for symmetric $CC^0$ circuits were also independently established by Pago (ICALP 2026) using different techniques. In the asymmetric regime, we establish degree upper bounds for depth three circuits of the form $MOD_p \circ MOD_m \circ AND_{O(1)}$ where $m=pq$ is a semiprime. This circuit class is a special case of the constant degree hypothesis, introduced by Barrington, Straubing and Therien (Inf. and Comp., 1990), where $m$ could be an arbitrary composite number. We argue that improved lower bounds for asymmetric torus polynomials approximating $AND$ imply size lower bounds for semiprime $m$ and hence progress on the constant-degree hypothesis.

Review history (2 revisions) →