In the 70's we had essentially no super-polynomial lower bounds for natural problems on general circuits beyond depth 2. Two papers kick started circuit complexity by independently showing no polynomial-size constant-depth family of circuits can compute the parity function (inputs with an odd number of ones).

Miklós Ajtai, Σ^{1}_{1}-Formulae
on Finite Structures, APAL, 1983.

Furst et al. developed random restrictions, i.e., randomly choose a set of variables and set them to 0 and 1 randomly. This will create a circuit on a smaller set of variables. For the parity function any such restricted circuit will compute parity (or its negation) on the unrestricted variables. They argue that the restricted circuit will give a polynomial-size circuit for parity of smaller depth. This leads to a contradiction because one can easily show that parity requires exponential-size depth-2 circuits.

Ajtai showed lower bounds against expressions described by first-order formula, equivalent to a uniform version of constant-depth circuits. I believe Ajtai's proof carries to the nonuniform case as well.

Furst et al. also show that super-quasipolynomial bounds for constant-depth parity circuits would imply an oracle relative to which the polynomial-time hierarchy differs from PSPACE. They don't achieve these stronger bounds but Yao does a few years later.

Håstad used
a more clever random restriction and much more difficult analysis to
create a *switching lemma* that implies essentially tight
exponential lower bounds for parity on constant depth
circuits. Razborov gives a simpler proof of the
switching lemma. Paul Beame has a nice self-contained write-up
of Razborov's proof and Fortnow and Laplante has a version using
Kolmogorov complexity. The simplest proof of the original
Furst-Saxe-Siper-Ajtai result comes from the lower bounds on circuits
with modulo p gates for some fixed prime p due to Razborov (in
Russian) and Smolensky. Alas,
Razborov and Smolensky's 1987 papers mark the last major
super-polynomial lower bounds for general circuit models.

> Ajtai showed lower bounds against

ReplyDelete> expressions described by first-order

> formula, equivalent to a uniform version

> of constant-depth circuits. I believe

> Ajtai's proof carries to the nonuniform

> case as well.

The inexpressibility result in Ajtai's

paper is stated and proved for

first-order formulae enriched

with arbitrary built-in predicates. This

takes care of non-uniform circuits already

(think of the built-in's as advice).