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

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.

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.