Browse Groups

• ## [Computational Complexity] Favorite Theorems: Parity

(1)
• NextPrevious
• August Edition 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
Message 1 of 1 , Sep 24, 2006
View Source
August Edition

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

Merrick Furst, James Saxe and Michael Sipser, Parity, Circuits, and the Polynomial-Time Hierarchy, FOCS 1981, MST 1984.

Miklós Ajtai, Σ11-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.

--
Posted by Lance to Computational Complexity at 9/24/2006 12:01:00 PM

Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.