Theory of Computing Seminar

Switching lemmas are a classic tool in complexity theory that are used to obtain some of the most powerful lower bounds in a diverse range of areas. In a celebrated work, Hastad proved a Switching lemma for (bounded-width) DNFs, which informally, shows the extent to which a DNF formula simplifies when some of the variables are set to 0 or 1 and some of the variables are left unset. Variants of that Switching lemma have been used in a wide range of areas, for obtaining lower bounds for circuit size and depth, oracle separations of complexity classes, Fourier analysis, computational learning, pseudorandomness, obtaining lower bounds on time, processor and memory of PRAMs, and complexity of proofs in bounded-depth proof systems, amongst others.

In this talk, i will try and talk about the following - (i) the basic definitions and objects involved in Switching lemmas (ii) A Switching lemma for functions more general than (bounded-width) DNFs (iii) Explicit functions that achieve the bounds in (ii), which turn out to be interesting in their own right.

Based on the paper - arxiv.org/abs/1703.00043