Opening The Switching Lemma: PRST Version
The Switching Lemma: PRST Version
- Length
- 55 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 7: Håstad's switching lemma
The switching lemma states that a small-width DNF or CNF under a random restriction collapses to a shallow decision tree with high probability. O'Donnell opens this CMU 15-855 session with Håstad's theorem and its parameters, noting that Håstad's proof inducts on the number of terms under strong conditioning hypotheses. A warm-up theorem bounds the restricted depth of a decision tree with a binomial random variable. Its key step shows that restricting and then following a random path equals taking a random path first. The main proof establishes the 2016 PRST switching lemma for W-clipped decision trees by combining a union bound, Markov's inequality and the th moment of a geometric variable. Graduate complexity and probability are assumed.

Your comment is kept while you sign up.Sign in
Proves the 2016 PRST switching lemma for W-clipped decision trees via random paths and geometric moments.
The switching lemma states that a small-width DNF or CNF under a random restriction collapses to a shallow decision tree with high probability. O'Donnell opens this CMU 15-855 session with Håstad's theorem and its parameters, noting that Håstad's proof inducts on the number of terms under strong conditioning hypotheses. A warm-up theorem bounds the restricted depth of a decision tree with a binomial random variable. Its key step shows that restricting and then following a random path equals taking a random path first. The main proof establishes the 2016 PRST switching lemma for W-clipped decision trees by combining a union bound, Markov's inequality and the th moment of a geometric variable. Graduate complexity and probability are assumed.
The Switching Lemma Primer
Computational Complexity: A Modern Approach
PRST '16
This lecture
Lecture 20 of 27 of Graduate Computational Complexity Theory.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.