We initiate the study of generalized AC^0 circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight \ge k (up to negations of the input bits), which we denote GC^0(k). The gate set of this class includes biased LTFs like the k-OR (outputs 1 iff \ge k bits are 1) and k-AND (outputs 0 iff \ge k bits are 0), and thus can be seen as an interpolation between AC^0 and TC^0.

We establish a tight multi-switching lemma for GC(k) circuits, which bounds the probability that several depth-2 GC^0(k) circuits do not simultaneously simplify under a random restriction. We also establish a new depth reduction lemma such that coupled with our multi-switching lemma, we can show many results obtained from the multi-switching lemma for depth-d size-s AC^0 circuits lifts to depth-d size-s^{.99} GC^0(.01\log s) circuits with no loss in parameters (other than hidden constants).

Our result has the following applications:

-Size-2^{\Omega(n^{1/d})} depth-d GC^0(\Omega(n^{1/d})) circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)).

-Size-n^{\Omega(\log n)} GC^0(\Omega(\log^2 n)) circuits with n^{.249} arbitrary threshold gates or n^{.499} arbitrary symmetric gates exhibit exponentially small correlation against an explicit function (extending a result of Tan and Servedio (RANDOM, 2019)).

-There is a seed length O((\log m)^{d-1}\log(m/\varepsilon)\log\log(m)) pseudorandom generator against size-m depth-d GC^0(\log m) circuits, matching the AC^0 lower bound of Håstad up to a \log\log m factor (extending a result of Lyu (CCC, 2022)).

-Size-m GC^0(\log m) circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)).

Improved presentation and layout, fixed minor inaccuracies and typos, added explicit circuit constructions matching our established lower bounds and correlation bounds

We initiate the study of generalized AC^0 circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight \ge k (up to negations of the input bits), which we denote GC^0(k). The gate set of this class includes biased LTFs like the k-OR (outputs 1 iff \ge k bits are 1) and k-AND (outputs 0 iff \ge k bits are 0), and thus can be seen as an interpolation between AC^0 and TC^0.

We establish a tight multi-switching lemma for GC(k) circuits, which bounds the probability that several depth-2 GC^0(k) circuits do not simultaneously simplify under a random restriction. We also establish a new depth reduction lemma such that coupled with our multi-switching lemma, we can show many results obtained from the multi-switching lemma for depth-d size-s AC^0 circuits lifts to depth-d size-s^{.99} GC^0(.01\log s) circuits with no loss in parameters (other than hidden constants).

Our result has the following applications:

-Size-2^{\Omega(n^{1/d})} depth-d GC^0(\Omega(n^{1/d})) circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)).

-Size-n^{\Omega(\log n)} GC^0(\Omega(\log^2 n)) circuits with n^{.249} arbitrary threshold gates or n^{.499} arbitrary symmetric gates exhibit exponentially small correlation against an explicit function (extending a result of Tan and Servedio (RANDOM, 2019)).

-There is a seed length O((\log m)^{d-1}\log(m/\varepsilon)\log\log(m)) pseudorandom generator against size-m depth-d GC^0(\log m) circuits, matching the AC^0 lower bound of Håstad up to a \log\log m factor (extending a result of Lyu (CCC, 2022)).

-Size-m GC^0(\log m) circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)).