Formal & Physical Sciences Computing & CybersecurityENQuasilinear Cook--Levin Theorem: Graduate Complexity Lecture 6 at CMURyan O'DonnellSeptember 22, 2017 77 min★ ★ ★ ★ ★ 5/5Cook-Levin TheoremQuasilinear TimeComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENProbabilistic Complexity Classes: Graduate Complexity Lecture 5 at CMURyan O'DonnellSeptember 19, 2017 80 min★ ★ ★ ★ ★ 5/5Complexity TheoryProbabilistic Turing MachinesBPP
Formal & Physical Sciences Computing & CybersecurityENHopcroft--Paul--Valiant Theorem: Graduate Complexity Lecture 3 at CMURyan O'DonnellSeptember 18, 2017 80 min★ ★ ★ ★ ★ 5/5Complexity TheorySpace ComplexityTime Complexity
Formal & Physical Sciences Computing & CybersecurityENHierarchy Theorems (Time, Space, and Nondeterministic): Graduate Complexity Lecture 2 at CMURyan O'DonnellSeptember 18, 2017 81 min★ ★ ★ ★ ★ 5/5Computational ComplexityHierarchy TheoremsTime Complexity
Formal & Physical Sciences Computing & CybersecurityENCourse Introduction and Overview: Graduate Complexity Lecture 1 at CMURyan O'DonnellSeptember 18, 2017 80 min★ ★ ★ ★ ★ 5/5Computational ComplexityComplexity ClassesTime Hierarchy
Formal & Physical Sciences Computing & CybersecurityENCircuits: Graduate Complexity Lecture 4 at CMURyan O'DonnellSeptember 18, 2017 79 min★ ★ ★ ★ ☆ 4/5CircuitsComplexity TheoryP/Poly
Formal & Physical Sciences Computing & CybersecurityENRyan O'Donnell tutorial on Hardess of Approximation - Part 3Ryan O'DonnellSeptember 7, 2017 63 min★ ★ ★ ★ ☆ 4/5Hardness of ApproximationUnique Games ConjectureMax-3Lin
Formal & Physical Sciences Computing & CybersecurityENRyan O'Donnell tutorial on Hardess of Approximation - Part 2Ryan O'DonnellSeptember 7, 2017 63 min★ ★ ★ ★ ☆ 4/5Hardness of ApproximationLabel CoverMax K-Cover
Formal & Physical Sciences Computing & CybersecurityENRyan O'Donnell tutorial on Hardess of Approximation - Part 1Ryan O'DonnellSeptember 7, 2017 58 min★ ★ ★ ★ ☆ 4/5Hardness of ApproximationComputational ComplexityNP-Hardness
Formal & Physical Sciences Computing & CybersecurityENSpring 2013 Lecture 07 Time Complexity default dade9f9eRyan O'DonnellJuly 15, 2017 71 min★ ★ ★ ★ ★ 5/5Time ComplexityAlgorithmsComputational Complexity
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Turing's Legacy (Spring 2015)Ryan O'DonnellJuly 15, 2017 69 min★ ★ ★ ★ ★ 5/5Turing MachineComputationAlgorithm
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Randomized Algorithms (Spring 2016)Ryan O'DonnellJuly 15, 2017 79 min★ ★ ★ ★ ★ 5/5Randomized AlgorithmsTheoretical Computer ScienceMarkov's Inequality
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Random Walks and Markov Chains (Spring 2016)Ryan O'DonnellJuly 15, 2017 79 min★ ★ ★ ★ ☆ 4/5Random WalksMarkov ChainsTheoretical Computer Science
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Probability 2 (Spring 2015)Ryan O'DonnellJuly 15, 2017 80 min★ ★ ★ ★ ★ 5/5ProbabilityRandom VariablesExpectation
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Probability 1 (Spring 2013)Ryan O'DonnellJuly 15, 2017 65 min★ ★ ★ ★ ☆ 4/5ProbabilityRandomized AlgorithmsConditional Probability
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Polynomials (Spring 2015)Ryan O'DonnellJuly 15, 2017 74 min★ ★ ★ ★ ☆ 4/5PolynomialsFinite FieldsError Correcting Codes
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: On Proofs (Spring 2016)Ryan O'DonnellJuly 15, 2017 63 min★ ★ ★ ★ ☆ 4/5ProofsTheoretical Computer ScienceMathematics
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Logic (Spring 2013)Ryan O'DonnellJuly 15, 2017 71 min★ ★ ★ ★ ☆ 4/5LogicPropositional LogicFirst-Order Logic
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Linear Algebra (Spring 2016)Ryan O'DonnellJuly 15, 2017 76 min★ ★ ★ ★ ☆ 4/5Linear AlgebraTheoretical Computer ScienceFibonacci
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Graphs: The Basics (Spring 2015)Ryan O'DonnellJuly 15, 2017 79 min★ ★ ★ ★ ☆ 4/5Graph TheoryTheoretical Computer ScienceLecture
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Finite Automata (Spring 2015)Ryan O'DonnellJuly 15, 2017 79 min★ ★ ★ ★ ★ 5/5Finite AutomataDFARegular Languages
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Epilogue: Why Max-Cut is My Favorite (Spring 2015)Ryan O'DonnellJuly 15, 2017 61 min★ ★ ★ ★ ★ 5/5Max-CutApproximation AlgorithmsSemidefinite Programming
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Deductive Systems (Spring 2015)Ryan O'DonnellJuly 15, 2017 81 min★ ★ ★ ★ ☆ 4/5Deductive SystemsPropositional LogicTheoretical Computer Science
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Countability and Diagonalization (Spring 2013)Ryan O'DonnellJuly 15, 2017 73 min★ ★ ★ ★ ★ 5/5CountabilityDiagonalizationCantor
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Computability (Spring 2013)Ryan O'DonnellJuly 15, 2017 79 min★ ★ ★ ★ ★ 5/5Turing MachineComputabilityDecidability
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 23: Open problemsRyan O'DonnellJuly 8, 2017 76 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisOpen Problems
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 19: Invariance theoremsRyan O'DonnellJuly 8, 2017 77 min★ ★ ★ ★ ★ 5/5Boolean FunctionsInvariance PrincipleCentral Limit Theorem
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 17: UG-hardness results from dictator testsJohn WrightJuly 8, 2017 84 min★ ★ ★ ★ ☆ 4/5Unique Games ConjectureDictator TestingHardness of Approximation
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 16: Håstad's hardness theoremsRyan O'DonnellJuly 8, 2017 78 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisHardness of Approximation
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 15: Constraint satisfacation problemsRyan O'DonnellJuly 8, 2017 75 min★ ★ ★ ★ ★ 5/5Constraint SatisfactionBoolean FunctionsHardness of Approximation
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 14: Probabilistically checkable proofs of proximityRyan O'DonnellJuly 8, 2017 76 min★ ★ ★ ★ ★ 5/5PCPProperty TestingBoolean Functions
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 13: Dictator Testing and the FKN TheoremRyan O'DonnellJuly 8, 2017 77 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisProperty Testing
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 11: Level-1 inequality and the 2/pi TheoremRyan O'DonnellJuly 8, 2017 79 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisLevel-1 Inequality
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 28: Why is P vs. NP Difficult?Ryan O'DonnellJuly 7, 2017 80 min★ ★ ★ ★ ★ 5/5P vs NPComputational ComplexityOracle Turing Machines
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 27: Hardness within PRyan O'DonnellJuly 7, 2017 82 min★ ★ ★ ★ ★ 5/5Complexity TheorySETHHardness Within P
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 26: Beyond Worst-Case AnalysisRyan O'DonnellJuly 7, 2017 80 min★ ★ ★ ★ ☆ 4/5Complexity TheoryPCP TheoremExponential Time Hypothesis
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 25: Interactive Proofs: IP=PSPACERyan O'DonnellJuly 7, 2017 83 min★ ★ ★ ★ ★ 5/5Interactive ProofsComplexity TheoryIP=PSPACE
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 24: Oracle Turing Machines and P^NPRyan O'DonnellJuly 7, 2017 82 min★ ★ ★ ★ ★ 5/5Computational ComplexityOracle Turing MachinesPolynomial Hierarchy
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 9: Majority, LTFs, and the CLTRyan O'DonnellJuly 7, 2017 77 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisLinear Threshold Functions
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 8: Linial--Mansour--Nisan TheoremsRyan O'DonnellJuly 7, 2017 74 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisCircuit Complexity
