We continue the study of the circuit class GC^0, which augments AC^0 with unbounded-fan-in gates that compute arbitrary functions inside a sufficiently small Hamming ball but must be constant outside it. While GC^0 can compute functions requiring exponential-size circuits, Kumar (CCC 2023) showed that switching-lemma lower bounds for AC^0 extend to GC^0 with no loss in parameters.

We prove a parallel result for the polynomial method: any lower bound for AC^0[p] obtained via the polynomial method extends to GC^0[p] without loss in parameters. As a consequence, we show that the majority function MAJ requires depth-$d$ GC^0[p] circuits of size $2^{\Omega(n^{1/2(d-1)})}$, matching the best-known lower bounds for AC^0[p]. This yields the most expressive class of non-monotone circuits for which exponential-size lower bounds are known for an explicit function. We also prove a similar result for the algorithmic method, showing that E^NP requires exponential-size GCC^0 circuits, extending a result of Williams (JACM 2014).

Finally, leveraging our improved classical lower bounds, we establish the strongest known unconditional separations between quantum and classical circuit classes. We separate QNC^0 from GC^0 and GC^0[p] in various settings and show that BQLOGTIME is not contained in GC^0. As a consequence, we construct an oracle relative to which BQP lies outside uniform GC^0, extending the Raz-Tal oracle separation between BQP and PH (STOC 2019).

We continue the study of the circuit class GC^0, which augments AC^0 with unbounded-fan-in gates that compute arbitrary functions inside a sufficiently small Hamming ball but must be constant outside it. While GC^0 can compute functions requiring exponential-size circuits, Kumar (CCC 2023) showed that switching-lemma lower bounds for AC^0 extend to GC^0 with no loss in parameters.

We prove a parallel result for the polynomial method: any lower bound for AC^0[p] obtained via the polynomial method extends to GC^0[p] without loss in parameters. As a consequence, we show that the majority function MAJ requires depth-$d$ GC^0[p] circuits of size $2^{\Omega(n^{1/2(d-1)})}$, matching the best-known lower bounds for AC^0[p]. This yields the most expressive class of non-monotone circuits for which exponential-size lower bounds are known for an explicit function. We also prove a similar result for the algorithmic method, showing that E^NP requires exponential-size GCC^0 circuits, extending a result of Williams (JACM 2014).

Finally, leveraging our improved classical lower bounds, we establish the strongest known unconditional separations between quantum and classical circuit classes. We separate QNC^0 from GC^0 and GC^0[p] in various settings and show that BQLOGTIME is not contained in GC^0. As a consequence, we construct an oracle relative to which BQP lies outside uniform GC^0, extending the Raz-Tal oracle separation between BQP and PH (STOC 2019).

Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class $GC^0$ that not only contains $AC^0$ but can---with a single gate---compute functions that require exponential-size $TC^0$ circuits. Their main result was that switching-lemma lower bounds for $AC^0$ lift to $GC^0$ with no loss in parameters, even though $GC^0$ requires exponential-size $TC^0$ circuits. Informally, $GC^0$ is $AC^0$ with unbounded-fan-in gates that behave arbitrarily inside a sufficiently small Hamming ball but must be constant outside it. While seemingly exotic, $GC^0$ captures natural circuit classes, such as circuits of biased linear threshold gates.  

We show that polynomial-method lower bounds for $AC^0[p]$ lift to $GC^0[p]$ with no loss in parameters, complementing Kumar's result for $GC^0$ and the switching lemma. As an application, we prove Majority requires depth-$d$ $GC^0[p]$ circuits of size $2^{\Omega(n^{1/2(d-1)})}$, matching the state-of-the-art lower bounds for $AC^0[p]$ proven by Razborov and Smolensky. We also apply the algorithmic method to show that $E^{NP}$ requires exponential-size $GCC^0$ circuits (the union of $GC^0[m]$ for all $m$), extending the result of Williams (JACM, 2014).

It is striking that the combinatorial switching lemma, the algebraic polynomial method, and the algorithmic method all generalize to $GC^0$-related classes, with the first two methods doing so without any loss in parameters. Notably, our results give the least restricted classes of non-monotone circuits for which we have exponential-size lower bounds for explicit functions.

By strengthening classical lower bounds from prior work, we also establish the strongest known unconditional separations between quantum and classical circuits. We prove:

1. $BQLOGTIME \not\subseteq GC^0$. This implies an oracle relative to which $BQP$ is not contained in the class of languages decidable by uniform families of size-$2^{n^{O(1)}}$ $GC^0$ circuits, generalizing Raz and Tal's relativized separation of $BQP$ from the polynomial hierarchy (STOC, 2019).  

2. There is a search problem that $QNC^0$ circuits can solve but is average-case hard for exponential-size $GC^0$ circuits.

3. For any prime $p$, there is a search problem that $QNC^0/qpoly$ circuits can solve but is average-case hard for exponential-size $GC^0[p]$ circuits.

4. For any prime $p$, there is an interactive problem that $QNC^0$ circuits can solve but exponential-size $GC^0[p]$ circuits cannot. 

title change and minor updates to the introduction

Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class $GC^0$ that not only contains $AC^0$ but can---with a single gate---compute functions that require exponential-size $TC^0$ circuits. Their main result was that switching-lemma lower bounds for $AC^0$ lift to $GC^0$ with no loss in parameters, even though $GC^0$ requires exponential-size $TC^0$ circuits. Informally, $GC^0$ is $AC^0$ with unbounded-fan-in gates that behave arbitrarily inside a sufficiently small Hamming ball but must be constant outside it. While seemingly exotic, $GC^0$ captures natural circuit classes, such as circuits of biased linear threshold gates.  

We show an analogous result for $GC^0[p]$ ($GC^0$ with $MOD_p$ gates) and the polynomial method. Specifically, we show that polynomial-method lower bounds for $AC^0[p]$ lift to $GC^0[p]$ with no loss in parameters. As an application, we prove Majority requires depth-$d$ $GC^0[p]$ circuits of size $2^{\Omega(n^{1/2(d-1)})}$, matching the state-of-the-art lower bounds for $AC^0[p]$ proven by Razborov and Smolensky. We also apply the algorithmic method to show that $E^{NP}$ requires exponential-size $GCC^0$ circuits (the union of $GC^0[m]$ for all $m$), extending the result of Williams (JACM, 2014).

It is striking that the combinatorial switching lemma, the algebraic polynomial method, and the algorithmic method all generalize to $GC^0$-related classes, with the first two methods doing so without any loss in parameters. Notably, our results give the least restricted classes of non-monotone circuits for which we have exponential-size lower bounds for explicit functions.

By strengthening classical lower bounds from prior work, we also establish the strongest known unconditional separations between quantum and classical circuits. We prove:

1. $BQLOGTIME \not\subseteq GC^0$. This implies an oracle relative to which $BQP$ is not contained in the class of languages decidable by uniform families of size-$2^{n^{O(1)}}$ $GC^0$ circuits, generalizing Raz and Tal's relativized separation of $BQP$ from the polynomial hierarchy (STOC, 2019).  

2. There is a search problem that $QNC^0$ circuits can solve but is average-case hard for exponential-size $GC^0$ circuits.

3. For any prime $p$, there is a search problem that $QNC^0/qpoly$ circuits can solve but is average-case hard for exponential-size $GC^0[p]$ circuits.

4. For any prime $p$, there is an interactive problem that $QNC^0$ circuits can solve but exponential-size $GC^0[p]$ circuits cannot.