Formal & Physical Sciences Computing & CybersecurityENThe Switching LemmaRyan O'DonnellAugust 30, 2021 30 min★ ★ ★ ★ ★ 5/5Switching LemmaHåstadAC0
Formal & Physical Sciences Computing & CybersecurityENIQIS Lecture 6.2 — Abstract computation and reversible computationArtur EkertMarch 8, 2021 17 min★ ★ ★ ★ ☆ 4/5Quantum ComputingReversible ComputationToffoli Gate
Formal & Physical Sciences Computing & CybersecurityENP=NP?Richard E BorcherdsJanuary 20, 2021 39 min★ ★ ★ ★ ☆ 4/5P vs NPComputational ComplexityPolynomial Time
Formal & Physical Sciences Computing & CybersecurityENAQIS '20: Zhengfeng Ji, Spooky complexity at a distanceZhengfeng JiDecember 22, 2020 67 min★ ★ ★ ★ ☆ 4/5Quantum ComplexityInteractive ProofsMIP*
Formal & Physical Sciences Computing & CybersecurityENAQIS '20: François Le Gall, Average-Case Quantum Advantage with Shallow CircuitsFrançois Le GallDecember 22, 2020 57 min★ ★ ★ ★ ☆ 4/5Quantum ComputingComplexity TheoryShallow Circuits
Formal & Physical Sciences Computing & CybersecurityENNoisy Variational Quantum Algorithm Simulation lecture by Yipeng HuangYipeng HuangAugust 9, 2020 55 min★ ★ ★ ★ ☆ 4/5Quantum ComputingVariational AlgorithmsQuantum Noise
Formal & Physical Sciences Computing & CybersecurityENDinur's proof of the PCP Theorem: the Powering step || @ CMU || Lecture 27d of CS Theory ToolkitRyan O'DonnellJuly 24, 2020 18 min★ ★ ★ ★ ☆ 4/5PCP TheoremDinur's ProofPowering Step
Formal & Physical Sciences Computing & CybersecurityENDinur's PCP: degree-reduction, expanderizing, mini-PCP || @ CMU || Lecture 27c of CS Theory ToolkitRyan O'DonnellJuly 23, 2020 25 min★ ★ ★ ★ ☆ 4/5PCP TheoremDinur's ProofExpander Graphs
Formal & Physical Sciences Computing & CybersecurityENDinur's Proof of the PCP Theorem: outline || @ CMU || Lecture 27b of CS Theory ToolkitRyan O'DonnellJuly 22, 2020 29 min★ ★ ★ ★ ★ 5/5PCP TheoremDinur's ProofGap Amplification
Formal & Physical Sciences Computing & CybersecurityENStatement of the PCP Theorem || @ CMU || Lecture 27a of CS Theory ToolkitRyan O'DonnellJuly 21, 2020 14 min★ ★ ★ ★ ★ 5/5PCP TheoremComputational ComplexityNP-Hardness
Formal & Physical Sciences Computing & CybersecurityENNP-Hardness of Approximation || @ CMU || Lecture 26e of CS Theory ToolkitRyan O'DonnellJuly 20, 2020 16 min★ ★ ★ ★ ★ 5/5NP-HardnessApproximation AlgorithmsLabel Cover
Formal & Physical Sciences Computing & CybersecurityENIntuition on models and their complexityDr. Eitan FarchiJuly 20, 2020 18 min★ ★ ★ ☆ ☆ 3/5Machine LearningModel ComplexityOverfitting
Formal & Physical Sciences Computing & CybersecurityENExponential Time Hypotheses: ETH and SETH || @ CMU || Lecture 26d of CS Theory ToolkitRyan O'DonnellJuly 17, 2020 23 min★ ★ ★ ★ ☆ 4/5ETHSETHFine-Grained Complexity
Formal & Physical Sciences Computing & CybersecurityENHardness of Random 3XOR and 3Sat || @ CMU || Lecture 26c of CS Theory ToolkitRyan O'DonnellJuly 16, 2020 23 min★ ★ ★ ★ ★ 5/53XOR3SatHardness
Formal & Physical Sciences Computing & CybersecurityENComputational Indistinguishability || @ CMU || Lecture 25b of CS Theory ToolkitRyan O'DonnellJuly 9, 2020 13 min★ ★ ★ ★ ☆ 4/5Computational IndistinguishabilityHybrid ArgumentCryptography
Formal & Physical Sciences Computing & CybersecurityENInformation Complexity || @ CMU || Lecture 24c of CS Theory ToolkitRyan O'DonnellJuly 7, 2020 28 min★ ★ ★ ★ ☆ 4/5Information ComplexityCommunication ComplexityMutual Information
Formal & Physical Sciences Computing & CybersecurityENYao's Minimax Theorem & IP_2's Communication Complexity || @ CMU || Lecture 23d of CS Theory ToolkitRyan O'DonnellJuly 2, 2020 19 min★ ★ ★ ★ ★ 5/5Communication ComplexityYao's Minimax TheoremFourier Analysis
Formal & Physical Sciences Computing & CybersecurityENRandomized Communication Complexity || @ CMU || Lecture 23c of CS Theory ToolkitRyan O'DonnellJuly 1, 2020 13 min★ ★ ★ ★ ★ 5/5Communication ComplexityRandomized AlgorithmsPublic Coins
Formal & Physical Sciences Computing & CybersecurityENDeterministic Communication Complexity || @ CMU || Lecture 23b of CS Theory ToolkitRyan O'DonnellJune 30, 2020 37 min★ ★ ★ ★ ★ 5/5Communication ComplexityDeterministic ProtocolsCombinatorial Rectangles
Formal & Physical Sciences Computing & CybersecurityENBasics of Communication Complexity || @ CMU || Lecture 23a of CS Theory ToolkitRyan O'DonnellJune 29, 2020 19 min★ ★ ★ ★ ★ 5/5Communication ComplexityTheory of ComputationLower Bounds
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Introduction (Spring 2016) reupload with improved audioRyan O'DonnellJune 28, 2020 72 min★ ★ ★ ★ ★ 5/5Theoretical Computer ScienceAlgorithmsComputation
Formal & Physical Sciences Computing & CybersecurityENTreewidth Definitions || @ CMU || Lecture 22b of CS Theory ToolkitRyan O'DonnellJune 25, 2020 32 min★ ★ ★ ★ ★ 5/5TreewidthGraph TheoryTheoretical Computer Science
Formal & Physical Sciences Computing & CybersecurityENPseudoexpectations || @ CMU || Lecture 21(d) of CS Theory ToolkitRyan O'DonnellJune 23, 2020 13 min★ ★ ★ ★ ☆ 4/5PseudoexpectationsSherali-AdamsSOS
Formal & Physical Sciences Computing & CybersecurityENThe Sum-of-Squares (SOS) Proof System || @ CMU || Lecture 21(c) of CS Theory ToolkitRyan O'DonnellJune 22, 2020 22 min★ ★ ★ ★ ☆ 4/5Sum-of-SquaresProof SystemsSemidefinite Programming
Formal & Physical Sciences Computing & CybersecurityENProof Complexity for CSPs || @ CMU || Lecture 21a of CS Theory ToolkitRyan O'DonnellJune 18, 2020 12 min★ ★ ★ ★ ☆ 4/5Proof ComplexityConstraint SatisfactionLinear Programming
Formal & Physical Sciences Computing & CybersecurityENCSP Approximability: Optimization and Certification || @ CMU || Lecture 20c of CS Theory ToolkitRyan O'DonnellJune 17, 2020 33 min★ ★ ★ ★ ★ 5/5CSPApproximation AlgorithmsCertification
Formal & Physical Sciences Computing & CybersecurityENConstraint Satisfaction Problems || @ CMU || Lecture 20b of CS Theory ToolkitRyan O'DonnellJune 16, 2020 31 min★ ★ ★ ★ ★ 5/5Constraint Satisfaction ProblemsDichotomy TheoremTheoretical Computer Science
Formal & Physical Sciences Computing & CybersecurityENGoemans--Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory ToolkitRyan O'DonnellJune 15, 2020 31 min★ ★ ★ ★ ★ 5/5Max-CutSDPGoemans-Williamson
Formal & Physical Sciences Computing & CybersecurityENThe SDP Relaxation for Max-Cut || @ CMU || Lecture 19b of CS Theory ToolkitRyan O'DonnellJune 11, 2020 33 min★ ★ ★ ★ ★ 5/5SDPMax-CutSemidefinite Programming
Formal & Physical Sciences Computing & CybersecurityENMin-st-Cut is the dual LP of Max-st-Flow || @ CMU || Lecture 18d of CS Theory ToolkitRyan O'DonnellJune 9, 2020 19 min★ ★ ★ ★ ★ 5/5Linear ProgrammingMax-Flow Min-CutDuality
Formal & Physical Sciences Computing & CybersecurityENRounding LP Solutions: Min-Vertex-Cover || @ CMU || Lecture 18c of CS Theory ToolkitRyan O'DonnellJune 8, 2020 17 min★ ★ ★ ★ ☆ 4/5Linear ProgrammingVertex CoverApproximation Algorithms
Formal & Physical Sciences Computing & CybersecurityENRelaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory ToolkitRyan O'DonnellJune 5, 2020 28 min★ ★ ★ ★ ★ 5/5Linear ProgrammingInteger Linear ProgrammingBipartite Matching
Formal & Physical Sciences Computing & CybersecurityENExpander Graph Application 2: Derandomization || @ CMU || Lecture 16c of CS Theory ToolkitRyan O'DonnellMay 4, 2020 22 min★ ★ ★ ★ ★ 5/5Expander GraphsDerandomizationRandomized Algorithms
Formal & Physical Sciences Computing & CybersecurityENCheeger's Inequality || @ CMU || Lecture 15d of CS Theory ToolkitRyan O'DonnellMay 3, 2020 61 min★ ★ ★ ★ ★ 5/5Cheeger's InequalitySpectral Graph TheoryLaplacian Eigenvalues
Formal & Physical Sciences Computing & CybersecurityENEpsilon-biased Generators || @ CMU || Lecture 12d of CS Theory ToolkitRyan O'DonnellApril 23, 2020 23 min★ ★ ★ ★ ★ 5/5Epsilon-Biased GeneratorsPseudorandomnessCoding Theory
Formal & Physical Sciences Computing & CybersecurityENImpagliazzo--Wigderson, and Nisan's PRGs || @ CMU || Lecture 12b of CS Theory ToolkitRyan O'DonnellApril 21, 2020 12 min★ ★ ★ ★ ☆ 4/5PseudorandomnessComplexity TheoryDerandomization
Formal & Physical Sciences Computing & CybersecurityENSpooky complexity at a distanceZhengfeng JiApril 20, 2020 77 min★ ★ ★ ★ ★ 5/5Quantum ComplexityMIP*Interactive Proofs
Formal & Physical Sciences Computing & CybersecurityENPseudorandom Generators || @ CMU || Lecture 12a of CS Theory ToolkitRyan O'DonnellApril 20, 2020 20 min★ ★ ★ ★ ☆ 4/5Pseudorandom GeneratorsComplexity TheoryBPP
Formal & Physical Sciences Computing & CybersecurityENMultivariate Polynomials and the Schwartz--Zippel Lemma || @ CMU || Lecture 10e of CS Theory ToolkitRyan O'DonnellMarch 28, 2020 18 min★ ★ ★ ★ ★ 5/5Schwartz-ZippelMultivariate PolynomialsFinite Fields
Formal & Physical Sciences Computing & CybersecurityENCommunication Complexity of Equality || @ CMU || Lecture 10d of CS Theory ToolkitRyan O'DonnellMarch 27, 2020 15 min★ ★ ★ ★ ★ 5/5Communication ComplexityPolynomialsFinite Fields
