Tight Correlation Bounds for Circuits Between AC0 and TC0

Vinayak M. Kumar

We initiate the study of generalized AC0 circuits comprised of negations and arbitrary unbounded fan-in gates that only need to be constant over inputs of Hamming weight $\ge k$, w…