Switching lemmas in the 80ies and today (Johan Håstad)
Channel: IRIF
Date: 2020-10-30

The first switching lemmas were proved in 1980ies and gave us lower bounds for the size of small-depth circuits. In particular they gave us optimal lower bounds for the size of circuits computing parity and proved that there are functions that have small circuits of depth d, but require (sub)-exponential size if the depth is restricted to d-1.

Some questions were left open in the 1980ies but have been resolved more recently. Two such questions are to establish sharp estimates for the best correlation with parity and to prove that the just mentioned hierarchy result can be established in an average case setting. Both these results used new variants of the switching lemma.

We survey these results and give an indication what modifications were needed to obtain the recent results.

If time permits we also discuss how yet other switching lemmas can be used to prove lower bounds for the length of Frege proofs using small-depth formulas.