## 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.