A Randomness-Efficient Replacement for G(k) Gates and an Improved Lower-Bound Consequence for GCC^0(k) Circuits

Abstract

We give a randomness-efficient probabilistic replacement for G(k) gates and derive an improved quantitative circuit lower-bound consequence for constant-depth GCC^0(k) circuits within the Williams algorithmic-method framework. For a G(k) gate of fan-in m and pointwise error \varepsilon, the construction usesO(k\log m+\log(1/\varepsilon))random bits and yields a constant-depth modular/AND representation whose logarithmic size and AND fan-in are bounded byO\!\left((k\log m+\log(1/\varepsilon))\log(1/\varepsilon)\right). At CircuitSAT scale, writing L=\log s, the resulting circuit-level parameters are total randomness O(kL) and logarithmic size and AND fan-in O(kL^2). Combining these parameters with the Grewal–Kumar/Williams SAT-to-lower-bound framework yields, for fixed circuit depth and admissible parameters, a lower-bound exponent\Lambda(n,k)=\min\left\{\frac{n^{3\eta/F}}{k},\frac{n^{2\eta/F}}{\sqrt{k}}\right\},where 1/2<\eta<1 and F=f(2d+O(1)) is the depth-dependent exponent arising in the symmetric-circuit conversion. Consequently, there exists a language in E^{NP} requiring nonuniform depth-d GCC^0(k) circuits of size\exp(\Omega(\Lambda(n,k))). On the common range of applicability, and when the same normalized depth-bound function is used, this improves the quantitative k-dependence obtained from the Grewal–Kumar algorithmic-method lower bound. The result is intentionally scoped to this circuit-complexity framework. It does not establish a lossless lifting of the full ACC^0 lower bound to GCC^0(k), and it does not resolve P versus NP.