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.