Ryan O'Donnell

@RyanODonnellTeaching

368 tuit · page 4/10

Formal & Physical Sciences Computing & Cybersecurity

Moments, Concentration, and Initializing an Array || @ CMU || Recitation 4 of CS Theory Toolkit

Ryan O'Donnell

February 9, 2022 71 min

★ ★ ★ ★ ☆ 4/5

CS TheoryConcentration InequalitiesArray Initialization

Formal & Physical Sciences Computing & Cybersecurity

Layer cakes and slivers || @ CMU || Recitation 3 of CS Theory Toolkit

Ryan O'Donnell

February 2, 2022 65 min

★ ★ ★ ★ ☆ 4/5

Stirling's FormulaBerry-Esseen TheoremLayer Cake Formula

Formal & Physical Sciences Computing & Cybersecurity

Inequalities, asymptotics, primes || @ CMU || Homework 1 / Recitation 2 of CS Theory Toolkit

Ryan O'Donnell

January 26, 2022 60 min

★ ★ ★ ★ ☆ 4/5

AsymptoticsInequalitiesPrime Number Theorem

Formal & Physical Sciences Mathematics

The Central Binomial Coefficient || @ CMU || Recitation 1 of CS Theory Toolkit

Ryan O'Donnell

January 19, 2022 60 min

★ ★ ★ ★ ★ 5/5

Central Binomial CoefficientAsymptoticsBig Theta

Formal & Physical Sciences Computing & Cybersecurity

Panteleev--Kalachev Codes: Asymptotically good quantum LDPC codes and classical LTCs

Ryan O'Donnell

December 24, 2021 67 min

★ ★ ★ ★ ★ 5/5

Quantum LDPC CodesLocally Testable CodesCoding Theory

Formal & Physical Sciences Computing & Cybersecurity

Quantum Computing with Just 1 Qubit | The Elitzur--Vaidman Bomb 'Algorithm'

Ryan O'Donnell

December 21, 2021 67 min

★ ★ ★ ★ ★ 5/5

Quantum ComputingQubitElitzur-Vaidman

Formal & Physical Sciences Computing & Cybersecurity

The Switching Lemma

Ryan O'Donnell

August 30, 2021 30 min

★ ★ ★ ★ ★ 5/5

Switching LemmaHåstadAC0

Formal & Physical Sciences Computing & Cybersecurity

Pauli error estimation via Population Recovery

Ryan O'Donnell

July 1, 2021 29 min

★ ★ ★ ★ ☆ 4/5

Quantum ComputingPauli ChannelsPopulation Recovery

Formal & Physical Sciences Computing & Cybersecurity

Improved Quantum Data Analysis (Shadow Tomography)

Ryan O'Donnell

February 6, 2021 58 min

★ ★ ★ ★ ☆ 4/5

Shadow TomographyQuantum ComputingAdaptive Data Analysis

Formal & Physical Sciences Mathematics

Fourier Analysis of Boolean Functions, in Harvard's CS 121 class. Learning, quantum, voting, & more!

Ryan O'Donnell

September 27, 2020 72 min

★ ★ ★ ★ ★ 5/5

Fourier AnalysisBoolean FunctionsCS 121

Formal & Physical Sciences Computing & Cybersecurity

Dinur's proof of the PCP Theorem: the Powering step || @ CMU || Lecture 27d of CS Theory Toolkit

Ryan O'Donnell

July 24, 2020 18 min

★ ★ ★ ★ ☆ 4/5

PCP TheoremDinur's ProofPowering Step

Formal & Physical Sciences Computing & Cybersecurity

Dinur's PCP: degree-reduction, expanderizing, mini-PCP || @ CMU || Lecture 27c of CS Theory Toolkit

Ryan O'Donnell

July 23, 2020 25 min

★ ★ ★ ★ ☆ 4/5

PCP TheoremDinur's ProofExpander Graphs

Formal & Physical Sciences Computing & Cybersecurity

Dinur's Proof of the PCP Theorem: outline || @ CMU || Lecture 27b of CS Theory Toolkit

Ryan O'Donnell

July 22, 2020 29 min

★ ★ ★ ★ ★ 5/5

PCP TheoremDinur's ProofGap Amplification

Formal & Physical Sciences Computing & Cybersecurity

Statement of the PCP Theorem || @ CMU || Lecture 27a of CS Theory Toolkit

Ryan O'Donnell

July 21, 2020 14 min

★ ★ ★ ★ ★ 5/5

PCP TheoremComputational ComplexityNP-Hardness

Formal & Physical Sciences Computing & Cybersecurity

NP-Hardness of Approximation || @ CMU || Lecture 26e of CS Theory Toolkit

Ryan O'Donnell

July 20, 2020 16 min

★ ★ ★ ★ ★ 5/5

NP-HardnessApproximation AlgorithmsLabel Cover

Formal & Physical Sciences Computing & Cybersecurity

Exponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory Toolkit

Ryan O'Donnell

July 17, 2020 23 min

★ ★ ★ ★ ☆ 4/5

ETHSETHFine-Grained Complexity

Formal & Physical Sciences Computing & Cybersecurity

Hardness of Random 3XOR and 3Sat || @ CMU || Lecture 26c of CS Theory Toolkit

Ryan O'Donnell

July 16, 2020 23 min

★ ★ ★ ★ ★ 5/5

3XOR3SatHardness

Formal & Physical Sciences AI — Models & Research

Learning Parity with Noise|| @ CMU || Lecture 26b of CS Theory Toolkit

Ryan O'Donnell

July 15, 2020 11 min

★ ★ ★ ★ ☆ 4/5

LPNCryptographyLearning With Errors

Formal & Physical Sciences Science — General & History

Learning With Errors (LWE) and Public Key Encryption || @ CMU || Lecture 25d of CS Theory Toolkit

Ryan O'Donnell

July 13, 2020 25 min

★ ★ ★ ★ ★ 5/5

LWEPublic Key EncryptionLattice-Based Cryptography

Formal & Physical Sciences Science — General & History

From One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit

Ryan O'Donnell

July 10, 2020 27 min

★ ★ ★ ★ ★ 5/5

CryptographyOne-Way FunctionsPseudorandom Generators

Formal & Physical Sciences Computing & Cybersecurity

Computational Indistinguishability || @ CMU || Lecture 25b of CS Theory Toolkit

Ryan O'Donnell

July 9, 2020 13 min

★ ★ ★ ★ ☆ 4/5

Computational IndistinguishabilityHybrid ArgumentCryptography

Formal & Physical Sciences Science — General & History

Intro to Cryptography || @ CMU || Lecture 25a of CS Theory Toolkit

Ryan O'Donnell

July 8, 2020 16 min

★ ★ ★ ★ ☆ 4/5

CryptographyOne-Time PadPerfect Secrecy

Formal & Physical Sciences Computing & Cybersecurity

Information Complexity || @ CMU || Lecture 24c of CS Theory Toolkit

Ryan O'Donnell

July 7, 2020 28 min

★ ★ ★ ★ ☆ 4/5

Information ComplexityCommunication ComplexityMutual Information

Formal & Physical Sciences Science — General & History

Mutual Information || @ CMU || Lecture 24b of CS Theory Toolkit

Ryan O'Donnell

July 6, 2020 28 min

★ ★ ★ ★ ★ 5/5

Mutual InformationInformation TheoryEntropy

Formal & Physical Sciences Science — General & History

Entropy || @ CMU || Lecture 24a of CS Theory Toolkit

Ryan O'Donnell

July 3, 2020 24 min

★ ★ ★ ★ ★ 5/5

EntropyInformation TheoryShannon Entropy

Formal & Physical Sciences Computing & Cybersecurity

Yao's Minimax Theorem & IP_2's Communication Complexity || @ CMU || Lecture 23d of CS Theory Toolkit

Ryan O'Donnell

July 2, 2020 19 min

★ ★ ★ ★ ★ 5/5

Communication ComplexityYao's Minimax TheoremFourier Analysis

Formal & Physical Sciences Computing & Cybersecurity

Randomized Communication Complexity || @ CMU || Lecture 23c of CS Theory Toolkit

Ryan O'Donnell

July 1, 2020 13 min

★ ★ ★ ★ ★ 5/5

Communication ComplexityRandomized AlgorithmsPublic Coins

Formal & Physical Sciences Computing & Cybersecurity

Deterministic Communication Complexity || @ CMU || Lecture 23b of CS Theory Toolkit

Ryan O'Donnell

June 30, 2020 37 min

★ ★ ★ ★ ★ 5/5

Communication ComplexityDeterministic ProtocolsCombinatorial Rectangles

Formal & Physical Sciences Computing & Cybersecurity

Basics of Communication Complexity || @ CMU || Lecture 23a of CS Theory Toolkit

Ryan O'Donnell

June 29, 2020 19 min

★ ★ ★ ★ ★ 5/5

Communication ComplexityTheory of ComputationLower Bounds

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Introduction (Spring 2016) reupload with improved audio

Ryan O'Donnell

June 28, 2020 72 min

★ ★ ★ ★ ★ 5/5

Theoretical Computer ScienceAlgorithmsComputation

Formal & Physical Sciences Computing & Cybersecurity

Algorithms for Bounded Treewidth || @ CMU || Lecture 22(c) of CS Theory Toolkit

Ryan O'Donnell

June 26, 2020 28 min

★ ★ ★ ★ ★ 5/5

TreewidthGraph AlgorithmsDynamic Programming

Formal & Physical Sciences Computing & Cybersecurity

Treewidth Definitions || @ CMU || Lecture 22b of CS Theory Toolkit

Ryan O'Donnell

June 25, 2020 32 min

★ ★ ★ ★ ★ 5/5

TreewidthGraph TheoryTheoretical Computer Science

Formal & Physical Sciences Mathematics

Trees and Series-Parallel Graphs || @ CMU || Lecture 22a of CS Theory Toolkit

Ryan O'Donnell

June 24, 2020 21 min

★ ★ ★ ★ ★ 5/5

TreewidthSeries-Parallel GraphsDynamic Programming

Formal & Physical Sciences Computing & Cybersecurity

Pseudoexpectations || @ CMU || Lecture 21(d) of CS Theory Toolkit

Ryan O'Donnell

June 23, 2020 13 min

★ ★ ★ ★ ☆ 4/5

PseudoexpectationsSherali-AdamsSOS

Formal & Physical Sciences Computing & Cybersecurity

The Sum-of-Squares (SOS) Proof System || @ CMU || Lecture 21(c) of CS Theory Toolkit

Ryan O'Donnell

June 22, 2020 22 min

★ ★ ★ ★ ☆ 4/5

Sum-of-SquaresProof SystemsSemidefinite Programming

Formal & Physical Sciences Mathematics

Sherali--Adams Proof System || @ CMU || Lecture 21b of CS Theory Toolkit

Ryan O'Donnell

June 19, 2020 36 min

★ ★ ★ ★ ☆ 4/5

Sherali-AdamsProof SystemsLP Relaxations

Formal & Physical Sciences Computing & Cybersecurity

Proof Complexity for CSPs || @ CMU || Lecture 21a of CS Theory Toolkit

Ryan O'Donnell

June 18, 2020 12 min

★ ★ ★ ★ ☆ 4/5

Proof ComplexityConstraint SatisfactionLinear Programming

Formal & Physical Sciences Computing & Cybersecurity

CSP Approximability: Optimization and Certification || @ CMU || Lecture 20c of CS Theory Toolkit

Ryan O'Donnell

June 17, 2020 33 min

★ ★ ★ ★ ★ 5/5

CSPApproximation AlgorithmsCertification

Formal & Physical Sciences Computing & Cybersecurity

Constraint Satisfaction Problems || @ CMU || Lecture 20b of CS Theory Toolkit

Ryan O'Donnell

June 16, 2020 31 min

★ ★ ★ ★ ★ 5/5

Constraint Satisfaction ProblemsDichotomy TheoremTheoretical Computer Science

Formal & Physical Sciences Computing & Cybersecurity

Goemans--Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory Toolkit

Ryan O'Donnell

June 15, 2020 31 min

★ ★ ★ ★ ★ 5/5

Max-CutSDPGoemans-Williamson