The Switching Lemma @RyanODonnellTeaching
The Switching Lemma  @RyanODonnellTeaching
Uploaded August 2021 | Updated November 2026, 1 day ago
A complete proof of Håstad's form of the Switching Lemma, following a long line of proof ideas from Furst--Saxe--Sipser through Thapen.

Opening tune "Switch" by Will Smith, Universal Music Group / Interscope.
Closing tune "Dancing Queen" by Abba, performed by Gunhild Carling and Scott Bradlee's Postmodern Jukebox.
Both used without permission, but I hope it's okay, it's all for educational purposes.
The Switching Lemma#6/100: Creating and destroying qubits || Quantum Computer Programming in 100 Easy LessonsEntropy || @ CMU || Lecture 24a of CS Theory ToolkitExpander Graph Application 2: Derandomization || @ CMU || Lecture 16c of CS Theory ToolkitHardness Assumptions Beyond NP ≠ P || @ CMU || Lecture 26a of CS Theory ToolkitDinurs proof of the PCP Theorem: the Powering step || @ CMU || Lecture 27d of CS Theory ToolkitFrom One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit#44/100: Discriminating 2 qubits, no false poss || Quantum Computer Programming in 100 Easy LessonsDinurs Proof of the PCP Theorem: outline || @ CMU || Lecture 27b of CS Theory Toolkit#91/100: All the planes of rotation for IncrL || Quantum Computer Programming in 100 Easy LessonsExponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory ToolkitSpectral Graph Theory: conductance and Sparsest-Cut || @ CMU || Lecture 15b of CS Theory Toolkit
Ryan ODonnell |

The Switching Lemma

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER