On CC\textsuperscript{0} Lower Bounds for AND via Torus Polynomials
2026-07-11 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study a type of circuit called CC^0, which uses special gates and is limited in depth and size, to see if it can compute the AND function efficiently. They focus on symmetric circuits, where inputs are treated equally, and use a technique involving approximating AND with mathematical objects called torus polynomials. By building on previous results about these approximations, they prove that such symmetric CC^0 circuits must be very large to compute AND. They also explore related cases with asymmetric circuits and connect their findings to an older open problem known as the constant-degree hypothesis.
CC^0 circuitsAND functiontorus polynomialssymmetric circuitscircuit lower boundsMOD_m gatesconstant-degree hypothesispolynomial approximationdepth-bounded circuitsasymmetric circuits
Authors
Vaibhav Krishan, Jayalal Sarma
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Ω(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.