On Some Recent Projection Switching Lemmas for Small Depth Circuits

Abstract

Switching Lemmas are an important technique for analyzing and proving
lower bounds for constant-depth Boolean circuits. Typically, in applying a
switching lemma, we restrict the circuit under consideration by setting a
few of the input variables to constants at random while leaving the other
variables unset. A Switching lemma guarantees, roughly, that any small
Boolean circuit simplifies considerably under such a restriction.
Recently, researchers have analyzed what happens to constant-depth circuits
under random projections, where in addition to the above, we also
identify some variables with each other. This analysis has yielded strong
Projection Switching Lemmas, which have been used to prove some new results
in Boolean circuit complexity, including the resolution of some long
standing open problems in the area. We review some of these projection
switching lemmas and their applications.