Favorite Theorem 2

Favorite Theorem 2

• Håstad:
  • Parity does not have depth d circuits with less than gates.
• Proof uses switching lemma to swap “AND” and “OR” levels.
• Switching Lemma proven by randomly restricting some inputs to 0 and 1.

Previous slide

Next slide

Back to the first slide

View Graphic Version

Earlier lower bounds by Furst-Saxe-Sipser and Yao. Both also use random restriction methods.