2026-08-10T22:48:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22883 2025-10-02T13:36:25Z ddc:004 open_access

Violating Constant Degree Hypothesis Requires Breaking Symmetry Kawałek, Piotr Weiß, Armin Circuit lower bounds constant degree hypothesis permutation groups CC⁰-circuits The Constant Degree Hypothesis was introduced by Barrington et. al. [David A. Mix Barrington et al., 1990] to study some extensions of q-groups by nilpotent groups and the power of these groups in a computation model called NuDFA (non-uniform DFA). In its simplest formulation, it establishes exponential lower bounds for MOD_q∘MOD_m∘AND_d circuits computing AND of unbounded arity n (for constant integers d,m and a prime q). While it has been proved in some special cases (including d = 1), it remains wide open in its general form for over 30 years. In this paper we prove that the hypothesis holds when we restrict our attention to symmetric circuits with m being a prime. While we build upon techniques by Grolmusz and Tardos [Vince Grolmusz and Gábor Tardos, 2000], we have to prove a new symmetric version of their Degree Decreasing Lemma and use it to simplify circuits in a symmetry-preserving way. Moreover, to establish the result, we perform a careful analysis of automorphism groups of MOD_m∘AND_d subcircuits and study the periodic behaviour of the computed functions. Our methods also yield lower bounds when d is treated as a function of n. Finally, we present a construction of symmetric MOD_q∘MOD_m∘AND_d circuits that almost matches our lower bound and conclude that a symmetric function f can be computed by symmetric MOD_q∘MOD_p∘AND_d circuits of quasipolynomial size if and only if f has periods of polylogarithmic length of the form p^k q^𝓁. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Piotr Kawałek and Armin Weiß 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.58 urn:nbn:de:0030-drops-228837 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.58 eng https://creativecommons.org/licenses/by/4.0/legalcode