## On implications of better sub-exponential lower bounds for AC0

by Roei Tell

The folklore presented in this work asserts results of the form if computing a function $f:\{0,1\}^n\to\{0,1\} by AC0 circuits of depth$d$requires size$exp(n^(3.001/(d-1)))$, then AC0[Sym] circuits of depth two that compute$f$must have size at least$n^2$. The conclusion follows also if AC0 circuits of depth six requires size$exp(n^0.667)$. Recalling that the best known size lower bound for explicit function asserts that AC0 circuits of size$d$requires size$exp(n^(1/(d-1)))\$, Roei views the foregoing implication as saying that significant improvements on our understanding of AC0 circuits in the sub-exponential regime would imply breakthroughts in the study of stronger computing devices such as AC0[Sym], linear threshold circuits of constant depth, and NC1.