On implications of better sub-exponential lower bounds for AC0

by Roei Tell

Oded's comments

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.

The original abstract (slightly revised)

Lower bounds for AC0 circuits of sub-exponential size have been known since the 1980s. The point of this text is to highlight the fact that lower bounds for AC0 circuits of significantly larger sub-exponential size imply lower bounds for polynomial-sized circuits from circuit classes such as AC0[Sym], linear threshold circuits of constant depth, and NC1.

Available from Roei's expositions page.


Back to list of Oded's choices.