Computational Complexity

Sunday, September 24, 2006

 
Favorite Theorems: Parity

Posted by Lance

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, Σ¹₁-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.

12:01 PM #

1.  Anonymous says:  
   
   > 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.
   
   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).
   

   4:37 AM, September 25, 2006