Formal & Physical Sciences Computing & CybersecurityENValiant--Vazirani Theorem, and Exact Counting (#P): Graduate Complexity Lecture 13 at CMURyan O'DonnellOctober 21, 2017 76 min★ ★ ★ ★ ★ 5/5Computational ComplexityValiant-Vazirani#P
Formal & Physical Sciences Computing & CybersecurityENApproximate counting: Graduate Complexity Lecture 12 at CMURyan O'DonnellOctober 21, 2017 79 min★ ★ ★ ★ ★ 5/5Computational ComplexityApproximate CountingInteractive Proofs
Formal & Physical Sciences Computing & CybersecurityENMore on constant-round interactive proof systems: Graduate Complexity Lecture 12 at CMURyan O'DonnellOctober 19, 2017 81 min★ ★ ★ ★ ★ 5/5Computational ComplexityInteractive ProofsMA
Formal & Physical Sciences Computing & CybersecurityENIntroduction to Arthur-Merlin classes, MA and AM: Graduate Complexity Lecture 10 at CMURyan O'DonnellOctober 19, 2017 82 min★ ★ ★ ★ ★ 5/5Complexity TheoryArthur-MerlinMA
Formal & Physical Sciences Computing & CybersecurityENTime/Space Tradeoffs for SAT: Graduate Complexity Lecture 9 at CMURyan O'DonnellOctober 3, 2017 91 min★ ★ ★ ★ ★ 5/5Complexity TheorySATTime-Space Tradeoff
Formal & Physical Sciences Computing & CybersecurityENThe Polynomial Time Hierarchy: Graduate Complexity Lecture 7 at CMURyan O'DonnellSeptember 29, 2017 79 min★ ★ ★ ★ ★ 5/5Complexity TheoryPolynomial HierarchyNP
Formal & Physical Sciences Computing & CybersecurityENOracles, and the Polynomial Time Hierarchy vs. circuits: Graduate Complexity Lecture 8 at CMURyan O'DonnellSeptember 29, 2017 82 min★ ★ ★ ★ ★ 5/5Computational ComplexityOracle Turing MachinesPolynomial Time Hierarchy
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 & CybersecurityENGreat Ideas in Theoretical Computer Science: Quantum Computing (Spring 2016)Ryan O'DonnellJuly 24, 2017 78 min★ ★ ★ ★ ☆ 4/5Quantum ComputingTheoretical Computer ScienceQubits
Formal & Physical Sciences Computing & CybersecurityENSpring 2015 Lecture 25 Quantum Computation defaultRyan O'DonnellJuly 15, 2017 82 min★ ★ ★ ★ ☆ 4/5Quantum ComputationReversible ComputationProbabilistic Computation
Formal & Physical Sciences Computing & CybersecurityENSpring 2013 Lecture 19 Quantum Computation default b4aea100Ryan O'DonnellJuly 15, 2017 79 min★ ★ ★ ★ ☆ 4/5Quantum ComputationReversible CircuitsProbabilistic Circuits
Formal & Physical Sciences Computing & CybersecurityENSpring 2013 Lecture 15 Approximation Algorithms defaultRyan O'DonnellJuly 15, 2017 73 min★ ★ ★ ★ ☆ 4/5Approximation AlgorithmsVertex CoverNP-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: Quantum Computing (Spring 2016)Ryan O'DonnellJuly 15, 2017 77 min★ ★ ★ ★ ☆ 4/5Quantum ComputingTheoretical Computer ScienceQubits
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: Group Theory (Spring 2016)Ryan O'DonnellJuly 15, 2017 80 min★ ★ ★ ★ ★ 5/5Group TheoryTheoretical Computer ScienceLagrange's Theorem
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: Graph Algorithms (Spring 2015)Ryan O'DonnellJuly 15, 2017 70 min★ ★ ★ ★ ☆ 4/5Graph AlgorithmsBFSDFS
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: Fast Integer Multiplication (Spring 2016)Ryan O'DonnellJuly 15, 2017 74 min★ ★ ★ ★ ☆ 4/5Integer MultiplicationFast Fourier TransformSchönhage-Strassen
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
