{"id":"cc6fbfbc-5c01-4c14-aa70-c5d910e1c015","arxiv_id":"2607.10236","paper_version":2,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Symmetric depth-h CC^0 circuits need size 2^{Ω̃(n^{1/O(h)})} to compute AND, via a symmetry-preserving torus-polynomial approximation of such circuits.","lead":"The paper proves exponential size lower bounds for symmetric constant-depth MOD circuits computing AND, via torus polynomial approximations. It also gives degree upper bounds for certain depth-three asymmetric circuits and links stronger torus lower bounds to progress on the constant-degree hypothesis.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"Abstract-only review cannot verify the claimed symmetry-preserving torus-polynomial construction that transfers Krishan–Vishwanathan degree bounds into the size lower bound.","rationale":"The reader correctly isolates the symmetry-preserving transfer as the weakest (and load-bearing) assumption and assigns CONDITIONAL / LOW confidence precisely because the abstract alone cannot certify it. My stress-test finds no stronger or different concern; the same missing construction is the single point on which the strongest claim stands or falls. No independent formal verification, code, or quantitative lemmas are present to raise confidence. Consequently the verdict remains CONDITIONAL pending full-text inspection of that transfer theorem, and agreement with the reader is complete.","tokens_in":2168,"tokens_out":503,"duration_ms":4547,"concrete_test":"Once the full text is available, extract the precise statement of the symmetry-preserving approximation theorem (claimed key ingredient) and recompute the degree of the resulting torus polynomial for a depth-h symmetric MOD_m circuit of size s; check whether that degree is O((log s)^{O(h)}) (or the exact bound asserted). If the degree is larger by more than a polylog factor, or if the approximation error exceeds the threshold required by Krishan–Vishwanathan, the size lower bound fails to transfer.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (any depth-h symmetric CC^0 circuit computing AND has size 2^{Ω̃(n^{1/O(h)})}) rests on a single transfer step: every symmetric CC^0 circuit admits a symmetric torus-polynomial approximation whose degree is controlled by size and depth so that the Krishan–Vishwanathan degree lower bounds apply directly. The abstract asserts an “explicit correspondence between the symmetry of the circuit and that of the polynomial” as the key ingredient, yet supplies neither the definition of circuit symmetry, the approximation error, nor the degree-control argument. Without those details it is impossible to confirm that the correspondence preserves the quantitative parameters needed for the exponential size bound; any gap in error accumulation or in the precise notion of symmetry would break the transfer. Concurrent independent work by Pago is disclosed, but does not substitute for verification of this paper’s construction.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":2393,"tokens_out":967,"duration_ms":20122,"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":[{"comment":"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.","section":"Abstract (symmetric size lower bound)"},{"comment":"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.","section":"Abstract (asymmetric regime / constant-degree hypothesis)"}],"minor_comments":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract"},{"comment":"Notation for the soft-O in the exponent (Ω̃) appears without expansion; writing the precise polylog factors once would remove ambiguity.","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"Only the abstract was available for this review; the full manuscript was not supplied. The report is therefore necessarily limited to logical outline and stated claims. I recommend that the editor obtain the complete text (including the symmetry-preserving construction, error analysis, and degree-control lemmas) before a final decision. The self-citation of Krishan–Vishwanathan is disclosed and is used as a black-box degree lower bound rather than a circular derivation; that is not itself a problem, but the transfer step that converts those degree bounds into circuit-size bounds is the part that must be checked carefully."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","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.\n\nWhat 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":2969,"tokens_out":579,"would_cite":false,"duration_ms":4298,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q06","68Q17"],"pacs":[],"model":"grok-4.5","headline":"Symmetric CC° circuits need superpolynomial size to compute AND, via torus-polynomial degree lower bounds.","keywords":["CC0 circuits","AND function","torus polynomials","symmetric circuits","degree lower bounds","constant-degree hypothesis","modular gates","circuit complexity"],"falsifier":"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.","tokens_in":3060,"feed_emoji":"∑","tokens_out":794,"duration_ms":6120,"temperature":0.7,"pith_summary":"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.","feed_headline":"Symmetric modular circuits need exponential size for AND","feed_subtitle":"Torus-polynomial degree bounds force 2 to a power of n to the 1 over O(depth)","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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°."],"fun_headline_variants":["Symmetric CC0 circuits need size 2^{Ω̃(n^{1/O(h)})} for AND","Torus degree bounds force exponential size on symmetric modular AND","Depth-h symmetric CC0 for AND requires 2 to the n^{1/O(h)} size","Symmetric modular circuits hit exponential size for computing AND","Symmetry of torus polys transfers AND lower bounds to CC0 size"],"cache_read_input_tokens":128,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Symmetric CC0 circuits need size 2^{Ω̃(n^{1/O(h)})} for AND","Torus degree bounds force exponential size on symmetric modular AND","Depth-h symmetric CC0 for AND requires 2 to the n^{1/O(h)} size","Symmetric modular circuits hit exponential size for computing AND","Symmetry of torus polys transfers AND lower bounds to CC0 size"]},"model":"grok-4.5","effort":"low","cost_usd":0.00675,"raw_usage":{"total_tokens":1779,"prompt_tokens":933,"num_sources_used":0,"completion_tokens":106,"cost_in_usd_ticks":67500000,"prompt_tokens_details":{"text_tokens":933,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":740,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":933,"tokens_out":106,"duration_ms":6158,"temperature":1.0,"reasoning_tokens":740,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-15T09:26:49.710417+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":2}