Formal & Physical Sciences Computing & CybersecurityENToda's 2nd Theorem and lower bounds for uniform ACC: Graduate Complexity Lecture 23 at CMURyan O'DonnellDecember 15, 2017 76 min★ ★ ★ ★ ★ 5/5Toda's TheoremACC CircuitsComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENRazborov--Smolensky lower bounds for AC0[p]: Graduate Complexity Lecture 22 at CMURyan O'DonnellDecember 15, 2017 72 min★ ★ ★ ★ ★ 5/5Circuit ComplexityLower BoundsAC0
Formal & Physical Sciences Computing & CybersecurityENIronic complexity: Graduate Complexity Lecture 27 at CMURyan O'DonnellDecember 15, 2017 79 min★ ★ ★ ★ ★ 5/5Complexity TheoryCircuit Lower BoundsNEXP
Formal & Physical Sciences Computing & CybersecurityENHardness vs. Randomness II: Graduate Complexity Lecture 25 at CMURyan O'DonnellDecember 15, 2017 77 min★ ★ ★ ★ ★ 5/5Complexity TheoryPseudorandomnessBPP
Formal & Physical Sciences Computing & CybersecurityENHardness vs. Randomness I: Graduate Complexity Lecture 24 at CMURyan O'DonnellDecember 15, 2017 82 min★ ★ ★ ★ ★ 5/5Computational ComplexityHardness vs RandomnessPseudorandom Generators
Formal & Physical Sciences Computing & CybersecurityENHardness amplification: Graduate Complexity Lecture 26 at CMURyan O'DonnellDecember 15, 2017 79 min★ ★ ★ ★ ★ 5/5Hardness AmplificationYao's XOR LemmaImpagliazzo's Hard-Core Set Lemma
Formal & Physical Sciences Computing & CybersecurityENMonotone circuit lower bounds: Graduate Complexity Lecture 21 at CMURyan O'DonnellNovember 19, 2017 83 min★ ★ ★ ★ ★ 5/5Complexity TheoryMonotone CircuitsLower Bounds
Formal & Physical Sciences Computing & CybersecurityENToda's 1st Theorem and the Permanent: Graduate Complexity Lecture 14 at CMURyan O'DonnellNovember 12, 2017 78 min★ ★ ★ ★ ★ 5/5Toda's TheoremPermanentComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENPermanent is #P-complete: Graduate Complexity Lecture 20 (out of order) at CMURyan O'DonnellNovember 12, 2017 73 min★ ★ ★ ★ ★ 5/5#P-CompletenessPermanentComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENThe Switching Lemma: PRST version: Graduate Complexity Lecture 19 at CMURyan O'DonnellNovember 8, 2017 55 min★ ★ ★ ★ ★ 5/5Switching LemmaComputational ComplexityCircuit Complexity
Formal & Physical Sciences Computing & CybersecurityENAlgebraic "NP vs. P" vs. "Boolean NP vs. P": Graduate Complexity Lecture 15 postscript at CMURyan O'DonnellNovember 7, 2017 14 min★ ★ ★ ★ ★ 5/5Computational ComplexityAlgebraic ComplexityP vs NP
Formal & Physical Sciences Computing & CybersecurityENRandom Restrictions and AC0 Circuit Lower Bounds: Graduate Complexity Lecture 18 at CMURyan O'DonnellNovember 5, 2017 79 min★ ★ ★ ★ ★ 5/5AC0Circuit Lower BoundsRandom Restrictions
Formal & Physical Sciences Computing & CybersecurityENIP = PSPACE: Graduate Complexity Lecture 17 at CMURyan O'DonnellNovember 5, 2017 78 min★ ★ ★ ★ ★ 5/5Computational ComplexityInteractive ProofsPSPACE
Formal & Physical Sciences Computing & CybersecurityENInstance Checking and the Permanent: Graduate Complexity Lecture 16 at CMURyan O'DonnellNovember 5, 2017 80 min★ ★ ★ ★ ★ 5/5Computational ComplexityPermanentInstance Checking
Formal & Physical Sciences Computing & CybersecurityENAlgebraic Circuit Complexity: Graduate Complexity Lecture 15 at CMURyan O'DonnellNovember 5, 2017 80 min★ ★ ★ ★ ★ 5/5Algebraic ComplexityArithmetic CircuitsComplexity Theory
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 & 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
![Razborov--Smolensky lower bounds for AC0[p]: Graduate Complexity Lecture 22 at CMU](https://i.ytimg.com/vi/TI-xKI3Uy4E/maxresdefault.jpg)
