$$

The proof is adapted from Hamed Hatami’s lecture notes for “COMP 531: Advanced Complexity Theory” at McGill. Hamed Hatami doesn’t condone my crappy metaphors.

This note presents Håstad’s original proof of his switching lemma.

Hermits and terrorists

You’re at a board game night, playing a very disturbing version of one-night werewolf. You don’t know how many players there are, but you know that tonight:

• some of the villagers are hermits, who will find their vocation and leave the village to go live in isolation;
• those who are not hermits have probability $p$ of being a terrorist, who will blow themselves up and kill everyone;
• the rest are normal villagers, who are fast asleep.

What’s the chance that at least $t$ villagers are still alive and present in the village the next day?

First of all, we can just disregard all the hermits. We don’t know how many non-hermits there are, but if at least $t$ people survive, then that means there were at least $t$ non-hermits, and all of them failed to be terrorists. That’s a pretty big surprise: the probability that they all fail to be terrorists was at most $(1-p{)}^t$! So regardless of how many non-hermits there were (and also regardless of how many people there were originally), the probability that $t$ people survive is $\le (1-p{)}^t$.

Here, crucially, we assumed they all independently had a $p$ chance of being a terrorist. If they were correlated (for example, if you know they’re either all terrorists or all non-terrorists), then the probability that at least $t$ people survive could be arbitrarily large, and we would have to know something about the number of people there were originally.

ANDs and ORs

The politically incorrect situation above is analogous to what happens to DNFs under random restrictions. Take some term $T_j$ of width $w$ in a DNF $f=T_1\vee \cdots \vee T_s$, and apply a random restriction $\rho$ with star probability $\delta$.

• If any of the variables in $T_j$ get set to $0$, then $T_j$ evaluates to $0$ and disappears from the DNF without affecting the other terms (i.e. $T_j$ is a hermit).¹
• On the other hand, assuming $T_j$ doesn’t get set to $0$ (all its variables were set to $1$ or $\ast$), there is a chance $p:=(\frac{1-\delta }{1+\delta }{)}^w$ that all of the variables in $T_j$ get set to $1$, in which case $T_j$ evaluates to $1$ and the whole DNF collapses to the constant $1$ (i.e. $T_j$ is a terrorist).

As long as $\delta =O(1/w)$, this probability $p$ of being a terrorist is a constant, and assuming these are all independent, this shows that

$$\mathrm{Pr}[f\upharpoonright {}_{\rho }\text{ has size }\ge t]\le (1-p{)}^t\le 2^{-\mathrm{\Omega }(t)}.$$

But the terms of a DNF tend to share a lot of variables,² so the events that two terms $T_{j_1}$ and $T_{j_2}$ are terrorists are far from independent: if $T_{j_1}$ and $T_{j_2}$ share a lot of the same variables, then conditioned on the fact that $T_{j_1}$ has some stars, $T_{j_2}$ is quite likely to have some stars too.

To rephrase, what goes wrong is: The terms shared some stars, which allowed them to both not be terrorists without it being a huge surprise.

It turns out this is the only issue! So if somehow after looking at $T_{j_1}$ we could fix all its stars, then it’s as if down the line, $T_{j_2}$ has a fresh $p$ chance of being a terrorist. Indeed, if we do that, the only variables we’ll have seen are all fixed to $0$ or $1$ (either by $\rho$ or by us), so conditioning on those should only increase the chance that the next term is a terrorist!

This insight then allows us to show that $f$ is very likely to be a small-depth decision tree. Indeed, say $T_{j_1}$ has $r$ stars. If we can inductively show that for all possible fixings of those $r$ stars, the resulting CNF has small decision tree depth, then so does $f$: just start out by querying those $r$ stars in the first $r$ levels.³

What we lost: a union bound

However, we did lose something: we now have to union-bound over all the possible assignments of those $r$ stars, and when the term isn’t a terrorist, that’s at least $2$ possibilities! So to counterbalance for this, it’s no longer enough for the probability $p$ of being a terrorist to be a constant; it should be at the very least $>1/2$! This means that we cannot say anything when $\delta$ is bigger than $1/w$…

And this union bound over the $2^r$ branches seems to be justified in practice. Indeed, consider the “choose your DNF” DNF:

$$f(x,y^{(1)},\dots ,y^{(2^w)})=x_1\cdots x_w{g}_1(y^{(1)})\vee x_1\cdots x_{w-1}\overline{x_w}{g}_2(y^{(2)})\vee \cdots \vee \overline{x_1}\cdots \overline{x_w}{g}_{2^w}(y^{(2^w)}).$$

where each $y^{(i)}$ is an input in ${\{0,1\}}^m$ and $g_j$ is itself a width-$w$ DNF (so that $f$ is a width-$2w$ DNF). Suppose that $r$ of the $w$ variables $x_1,\dots ,x_w$ end up being stars in $\rho$, then $2^r$ of the $g_j$’s will still be relevant after the restriction. So even pretty rare events about the structure of the $g_j$’s after the random restriction (like “$g_j\upharpoonright {}_{\rho }$ has large decision tree depth”) could end up happening: they’re all independent and there’s $2^r$ of them, so the probability that at least one of them happens is roughly $2^r$ bigger than the probability of any specific one happening!

Nevertheless, this case is not actually problematic for say $\delta =10/w$, since the probability to have $r$ stars in the first $w$ variables itself decreases very quickly (on the order of $r^{-\mathrm{\Omega }(r)}$, as mentioned in this earlier footnote³). It would be very interesting to still be able to say something beyond the $\delta =1/w$ barrier.

Statement and proof

Let $f=T_1\vee \cdots \vee T_s$ be a width-$w$ DNF, and let $\rho$ be a random restriction with star probability $\delta$. Håstad’s switching lemma⁴ says that for any $t>0$,

$$\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t]\le (C\delta w{)}^t$$

(for some constant $C$ to be set later).

We want to show that by induction: looking at the first non-hermit term $T_j$, then recursing on the rest of the DNF after fixing all its stars to $0$ or $1$. But this requires us to condition on $T_1,\dots ,T_{j-1}$ being hermits, and on the other variables in $T_j$ having the values that they had. Intuitively, this is fine, because those things only make it less likely to have stars going forward. But we do need to strengthen the induction hypothesis in order to handle this conditioning.

What we’ll actually prove is that for any auxiliary function $F:{\{0,1\}}^n\to \{0,1\}$, then

$$\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0]\le (C\delta w{)}^t.$$

This condition “$F\upharpoonright {}_{\rho }\equiv 0$” will be enough to encode all the things we wanted to condition on. And indeed, intuitively, conditioning on some function collapsing to a constant seems to only make it less likely for stars to appear.

We’ll induce on $s$, the number of terms of $f$. The base case when $f$ has no terms is obvious: that makes $f$ constant, so $\mathrm{DT}(f)=0$. Otherwise, look at the first term in $f$, i.e. $T_1$.

We can split the event $\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t$ into two cases: either $T_1\upharpoonright {}_{\rho }\equiv 0$ (i.e. $T_1$ is a hermit), or $T_1\upharpoonright {}_{\rho }\not\equiv 0$ (it’s not). It suffices to show that conditioned on either of those, the probability is $\le (C\delta w{)}^t$.

Case 1: $T_1$ is a hermit

Nothing interesting happens here: we’re just showing that “conditioning on the first few terms being hermits” can be achieved by “conditioning on some auxiliary function $F$ collapsing to $0$”.

We want to bound $\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0\wedge T_1\upharpoonright {}_{\rho }\equiv 0]$. We can observe two things:

• Once we’ve conditioned on $T_1$ collapsing to $0$, then $f$ is equivalent $T_2\vee \cdots \vee T_s$, and so their depths are the same.
• Conditioning on $F$ and $T_1$ both collapsing to $0$ is the same as conditioning on their OR $F\vee T_1$ collapsing to $0$.

So we can rewrite

$$\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0\wedge T_1\upharpoonright {}_{\rho }\equiv 0]=\mathrm{Pr}[\mathrm{DT}((T_2\vee \cdots \vee T_s)\upharpoonright {}_{\rho })\ge t\mid (F\vee T_1)\upharpoonright {}_{\rho }\equiv 0],$$

and then the induction hypothesis for $f^{\prime }:=T_2\vee \cdots \vee T_s$ and $F^{\prime }:=F\vee T_1$ tells us that the RHS is at most $(C\delta w{)}^t$.

Case 2: $T_1$ is not a hermit

This is the interesting case.

Without loss of generality (up to a flipping of the variables), we can assume that $T_1$ contains no negations. This means that under our assumption that $T_1\upharpoonright {}_{\rho }\not\equiv 0$, all the variables in $T_1$ are set either $1$ or $\ast$. We will roughly split the argument into two parts

• the probability to get $r$ stars in $T_1$ decreases fast as $r$ grows;
• the probability that “the rest of $f$ after fixing those stars” has depth $\ge t-r$ is small.

First, split into cases based on the subset $S\subseteq T_1$ of the variables in $T_1$ that are set to $\ast$:

$$\begin{array}{rl}& \mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0,T_1\upharpoonright {}_{\rho }\not\equiv 0]\\ =& \mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_{T_1}\in \{1,\ast \}]\\ =& \sum _{S\subseteq T_1}\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t,{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1\mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_{T_1}\in \{1,\ast \}]\\ =& \sum _{r=1}^w\sum _{\begin{array}{c}S\subseteq T_1\\ |S|=r\end{array}}\mathrm{Pr}[{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1\mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_{T_1}\in \{1,\ast \}]\cdot \mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1]\\ \le & \sum _{r=1}^w\underset{\text{(a): ``}\mathrm{Pr}[T_1\text{ has }r\text{ stars}]\text{''}}{\underbrace{\sum _{\begin{array}{c}S\subseteq T_1\\ |S|=r\end{array}}\mathrm{Pr}[{\rho }_S=\ast \mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_{T_1}\in \{1,\ast \}]}}\cdot \underset{\text{(b): ``}\mathrm{Pr}[\text{the rest of }f\text{ has depth }\ge t-r]\text{''}}{\underbrace{\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1]}}\end{array}$$

(note that we’re using shortcuts like “${\rho }_{T_1}\in \{1,\ast \}$” to mean “$\rho$ sets all of the variables of $T_1$ to either $1$ or $\ast$”). A crucial step in the above was to exclude the case $S=\mathrm{\varnothing }$. We can do this because when there are no stars, $T_1$ is a terrorist: it evaluates to $1$ and collapses the whole function to the constant $1$, which sets the decision tree depth to $0$.

Part (a): $T_1$ is unlikely to have many stars

First, we deal with the sum $\sum _{\begin{array}{c}S\subseteq T_1\\ |S|=r\end{array}}\mathrm{Pr}[{\rho }_S=\ast \mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_{T_1}\in \{1,\ast \}]$, which represents the probability that $T_1$ has at least $r$ stars (conditioned on being all $1$ and $\ast$). These probabilities would be trivial to compute if only we were not conditioning on $F\upharpoonright {}_{\rho }\equiv 0$: we have

$$\mathrm{Pr}[{\rho }_S=\ast \mid {\rho }_{T_1}\in \{1,\ast \}]={\left(\frac{\mathrm{Pr}[{\rho }_i=1]}{\mathrm{Pr}[{\rho }_i\in \{1,\ast \}]}\right)}^r={\left(\frac{\delta }{\frac{1+\delta }{2}}\right)}^r\le (2\delta {)}^r.$$

We want to somehow argue that conditioning on $F\upharpoonright {}_{\rho }\equiv 0$ can only decrease the probability that ${\rho }_S=\ast$. By Bayes’ rule, it suffices to prove the opposite: that conditioning on ${\rho }_S=\ast$ can only decrease the probability of $F\upharpoonright {}_{\rho }\equiv 0$, that is

$$\mathrm{Pr}[F\upharpoonright {}_{\rho }\equiv 0\mid {\rho }_S=\ast ,{\rho }_{T_1}\in \{1,\ast \}]\le \mathrm{Pr}[F\upharpoonright {}_{\rho }\equiv 0\mid {\rho }_{T_1}\in \{1,\ast \}].$$

We’re comparing two situations. In both of them, we’re forcing $\rho$ to take values $1$ and $\ast$ over $T_1\setminus S$. But in the first situation, we’re forcing ${\rho }_S=\ast$, while in the second one we’re only forcing ${\rho }_S\in \{1,\ast \}$. Clearly, if $F$ becomes fixed to $0$ in the first situation, it will still be fixed to $0$ in the second situation where some of its stars in $S$ are fixed to $1$’s.⁵

Therefore, we obtain⁶

$$\begin{array}{rl}\sum _{\begin{array}{c}S\subseteq T_1\\ |S|=r\end{array}}\mathrm{Pr}[{\rho }_S=\ast \mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_{T_1}\in \{1,\ast \}]& \le \sum _{\begin{array}{c}S\subseteq T_1\\ |S|=r\end{array}}\mathrm{Pr}[{\rho }_S=\ast \mid {\rho }_{T_1}\in \{1,\ast \}]\\ & \le \sum _{\begin{array}{c}S\subseteq T_1\\ |S|=r\end{array}}(2\delta {)}^r\\ & \le (\genfrac{}{}{0ex}{}{w}{r})(2\delta {)}^r\\ & \le (2\delta w{)}^r.\end{array}$$

Part (b): the rest is unlikely to be deep

To bound the probability $\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1]$, it suffices to union bound over all possible fixings $\sigma \in {\{0,1\}}^S$ of the stars: indeed, if $f\upharpoonright {}_{\sigma \rho }$ has decision tree depth $<t-r$ for each $\sigma$, then $f\upharpoonright {}_{\rho }$ must have decision tree depth $<t$.

• If $\sigma =1^S$, then $T_1$ gets set to $1$, so $f\upharpoonright {}_{\sigma \rho }\equiv 1$, so $\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\sigma \rho })\ge t-r\mid \cdot ]=0$ and we can just drop that case.
• Otherwise, $T_1$ gets set to $0$, so $f\upharpoonright {}_{\sigma \rho }\equiv (T_2\vee \cdots \vee T_s)\upharpoonright {}_{\sigma \rho }$. This will allow us to induce on $f^{\prime }:=(T_2\vee \cdots \vee T_s)\upharpoonright {}_{\sigma }$, which has less terms than $f$.

But in order to apply the inductive hypothesis, we also need to somehow get rid of the conditioning on ${\rho }_S=\ast$ and incorporate ${\rho }_{T_1\setminus S}=1$ into a the condition $F\upharpoonright {}_{\rho }\equiv 0$. To do this, observe that:

• conditioned on ${\rho }_S=\ast$, $F\upharpoonright {}_{\rho }\equiv 0$ holds iff it holds under every possible fixing of the variables in $S$: that is, $F$ can be replaced by $\underset{{\sigma }^{\prime }\in {\{0,1\}}^S}{\bigvee }F\upharpoonright {}_{{\sigma }^{\prime }}$;⁷
• to make sure that ${\rho }_{T_1\setminus S}=1$, it suffices to add $\underset{i\in T_1\setminus S}{\bigvee }\overline{x_i}$ to $F$.

All in all, “$F\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1$” is equivalent to “$F^{\prime }\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast$”, where the new function

$$F^{\prime }:=(\underset{{\sigma }^{\prime }\in {\{0,1\}}^S}{\bigvee }F\upharpoonright {}_{{\sigma }^{\prime }})\vee \left(\underset{i\in T_1\setminus S}{\bigvee }\overline{x_i}\right)$$

doesn’t depend on the variables in $S$ anymore.

This gives us

$$\begin{array}{rl}\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t& \mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1]\\ & \le \sum _{\sigma \in {\{0,1\}}^S}\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\sigma \rho })\ge t-r\mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1]\\ & =\sum _{\sigma \in {\{0,1\}}^S}\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\sigma \rho })\ge t-r\mid F^{\prime }\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast ]\\ & =\sum _{\sigma \in {\{0,1\}}^S}\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\sigma \rho })\ge t-r\mid F^{\prime }\upharpoonright {}_{\rho }\equiv 0]\\ & =\sum _{\begin{array}{c}\sigma \in {\{0,1\}}^S\\ \sigma \ne 1^S\end{array}}\mathrm{Pr}[\mathrm{DT}((\underset{f^{\prime }}{\underbrace{(T_2\vee \cdots \vee T_s)\upharpoonright {}_{\sigma }}})\upharpoonright {}_{\rho })\ge t-r\mid F^{\prime }\upharpoonright {}_{\rho }\equiv 0]\\ & \le \sum _{\begin{array}{c}\sigma \in {\{0,1\}}^S\\ \sigma \ne 1^S\end{array}}(C\delta w{)}^{t-r}\\ & \le 2^r(C\delta w{)}^{t-r},\end{array}$$

where the second equality holds because neither $f\upharpoonright {}_{\sigma }$ nor $F^{\prime }$ depend on the variables in $S$.

Putting (a) and (b) together

Coming back to our sum, we have

$$\begin{array}{rl}\mathrm{Pr}[& \mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0,T_1\upharpoonright {}_{\rho }\not\equiv 0]\\ & \le \sum _{r=1}^w\underset{\text{(a): ``}\mathrm{Pr}[T_1\text{ has }r\text{ stars}]\text{''}}{\underbrace{\sum _{\begin{array}{c}S\subseteq T_1\\ |S|=r\end{array}}\mathrm{Pr}[{\rho }_S=\ast \mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_{T_1}\in \{1,\ast \}]}}\cdot \underset{\text{(b): ``}\mathrm{Pr}[\text{the rest of }f\text{ has depth }\ge t-r]\text{''}}{\underbrace{\mathrm{Pr}[\mathrm{DT}(f\upharpoonright {}_{\rho })\ge t\mid F\upharpoonright {}_{\rho }\equiv 0,{\rho }_S=\ast ,{\rho }_{T_1\setminus S}=1]}}\\ & \le \sum _{r=1}^w(2\delta w{)}^r\cdot 2^r(C\delta w{)}^{t-r}\\ & \le (C\delta w{)}^t\cdot \sum _{r=1}^w(4/C{)}^r.\end{array}$$

It then suffices to set $C:=8$ in order to bound the sum $\sum _{r=1}^w(4/C{)}^r$ by $1$ and prove the lemma.

1. When $w$ is at least somewhat large, this is by far the most common outcome: the chance that no variable in $T_j$ gets set to $0$ is only $(\frac{1+\delta }{2}{)}^w=2^{-\mathrm{\Omega }(w)}$. But Håstad’s switching lemma doesn’t use this fact at all! ↩

2. If they don’t (i.e. if $f$ is read-once), then the above reasoning is completely valid, though! ↩

3. To make this complete, we also have to argue that $r$ won’t be too big, but this is the case. In fact, the probability that $T_{j_1}$ has $r$ stars decreases as $r^{-\mathrm{\Omega }(r)}$, because we’re counterbalancing a union bound $(\genfrac{}{}{0ex}{}{w}{r})\le w^r/r!$ over the choice of the $r$ variables with a probability ${\delta }^r=O(1/w{)}^r$. ↩ ↩²

4. Johan Håstad, “Computational limitations of small-depth circuits” (PhD thesis). ↩

5. This is not quite formal, but can be made formal by first drawing ${\rho }_{[n]\setminus S}$, then drawing ${\rho }_S$ (which is okay to do because all coordinates of $\rho$ are independent). ↩

6. Note that we’re not using the factor $1/r!$ that we could have gotten from the binomial $(\genfrac{}{}{0ex}{}{w}{r})$. In this case, it would only help us improve the constant $C$ slightly. ↩

7. Instead of applying this ORing trick, Håstad instead makes the induction hypothesis more general by allowing $f$ and $\rho$ to be defined on a subset $I\subseteq [n]$ of the variables whereas $F$ remains a function over all $n$ variables ($F\upharpoonright {}_{\rho }$ is understood to leave the variables outside of $I$ unfixed). In that case, we can replace $\rho$ by its projection ${\rho }^{\prime }$ on $[n]\setminus S$, which doesn’t change anything because under the assumption ${\rho }_S=\ast$, we have $f\upharpoonright {}_{\sigma \rho }\equiv f\upharpoonright {}_{\sigma {\rho }^{\prime }}$ and $F\upharpoonright {}_{\rho }\equiv F\upharpoonright {}_{{\rho }^{\prime }}$. And once that’s done, the conditioning ${\rho }_S=\ast$ disappears because ${\rho }^{\prime }$ doesn’t depend on ${\rho }_S$. ↩