Ryan O'Donnell

@RyanODonnellTeaching

369 tuit · page 8/10

Formal & Physical Sciences Computing & Cybersecurity

Hierarchy Theorems (Time, Space, and Nondeterministic): Graduate Complexity Lecture 2 at CMU

Ryan O'Donnell

September 18, 2017 81 min

★ ★ ★ ★ ★ 5/5

Computational ComplexityHierarchy TheoremsTime Complexity

Formal & Physical Sciences Computing & Cybersecurity

Course Introduction and Overview: Graduate Complexity Lecture 1 at CMU

Ryan O'Donnell

September 18, 2017 80 min

★ ★ ★ ★ ★ 5/5

Computational ComplexityComplexity ClassesTime Hierarchy

Formal & Physical Sciences Computing & Cybersecurity

Circuits: Graduate Complexity Lecture 4 at CMU

Ryan O'Donnell

September 18, 2017 79 min

★ ★ ★ ★ ☆ 4/5

CircuitsComplexity TheoryP/Poly

Formal & Physical Sciences Computing & Cybersecurity

Ryan O'Donnell tutorial on Hardess of Approximation - Part 3

Ryan O'Donnell

September 7, 2017 63 min

★ ★ ★ ★ ☆ 4/5

Hardness of ApproximationUnique Games ConjectureMax-3Lin

Formal & Physical Sciences Computing & Cybersecurity

Ryan O'Donnell tutorial on Hardess of Approximation - Part 2

Ryan O'Donnell

September 7, 2017 63 min

★ ★ ★ ★ ☆ 4/5

Hardness of ApproximationLabel CoverMax K-Cover

Formal & Physical Sciences Computing & Cybersecurity

Ryan O'Donnell tutorial on Hardess of Approximation - Part 1

Ryan O'Donnell

September 7, 2017 58 min

★ ★ ★ ★ ☆ 4/5

Hardness of ApproximationComputational ComplexityNP-Hardness

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Quantum Computing (Spring 2016)

Ryan O'Donnell

July 24, 2017 78 min

★ ★ ★ ★ ☆ 4/5

Quantum ComputingTheoretical Computer ScienceQubits

Formal & Physical Sciences Mathematics

Spring 2016 Lecture 17 Probability 1 default c543378d

Ryan O'Donnell

July 15, 2017 77 min

★ ★ ★ ★ ☆ 4/5

ProbabilityLectureMathematics

Formal & Physical Sciences Computing & Cybersecurity

Spring 2015 Lecture 25 Quantum Computation default

Ryan O'Donnell

July 15, 2017 82 min

★ ★ ★ ★ ☆ 4/5

Quantum ComputationReversible ComputationProbabilistic Computation

Formal & Physical Sciences Mathematics

Spring 2015 Lecture 23 Linear Algebra default

Ryan O'Donnell

July 15, 2017 73 min

★ ★ ★ ★ ☆ 4/5

Linear AlgebraEigenvaluesEigenvectors

Formal & Physical Sciences Mathematics

Spring 2015 Lecture 18 Probability 2

Ryan O'Donnell

July 15, 2017 80 min

★ ★ ★ ★ ☆ 4/5

ProbabilityRandom VariablesExpectation

Formal & Physical Sciences Mathematics

Spring 2015 Lecture 17 Probability 1 default

Ryan O'Donnell

July 15, 2017 78 min

★ ★ ★ ★ ☆ 4/5

ProbabilityRandomized AlgorithmsComputer Science

Formal & Physical Sciences Mathematics

Spring 2015 Lecture 16 Godel's Incompleteness Theorems default

Ryan O'Donnell

July 15, 2017 78 min

★ ★ ★ ★ ☆ 4/5

GödelIncompletenessLogic

Formal & Physical Sciences Computing & Cybersecurity

Spring 2013 Lecture 19 Quantum Computation default b4aea100

Ryan O'Donnell

July 15, 2017 79 min

★ ★ ★ ★ ☆ 4/5

Quantum ComputationReversible CircuitsProbabilistic Circuits

Formal & Physical Sciences Mathematics

Spring 2013 Lecture 18 Random Walks default 70d4e4b6

Ryan O'Donnell

July 15, 2017 78 min

★ ★ ★ ★ ☆ 4/5

Markov ChainsRandom WalksStochastic Processes

Formal & Physical Sciences Mathematics

Spring 2013 Lecture 15 Polynomials default ee567245

Ryan O'Donnell

July 15, 2017 73 min

★ ★ ★ ★ ☆ 4/5

PolynomialsFieldsFinite Fields

Formal & Physical Sciences Computing & Cybersecurity

Spring 2013 Lecture 15 Approximation Algorithms default

Ryan O'Donnell

July 15, 2017 73 min

★ ★ ★ ★ ☆ 4/5

Approximation AlgorithmsVertex CoverNP-Hardness

Formal & Physical Sciences Computing & Cybersecurity

Spring 2013 Lecture 07 Time Complexity default dade9f9e

Ryan O'Donnell

July 15, 2017 71 min

★ ★ ★ ★ ★ 5/5

Time ComplexityAlgorithmsComputational Complexity

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Turing's Legacy (Spring 2015)

Ryan O'Donnell

July 15, 2017 69 min

★ ★ ★ ★ ★ 5/5

Turing MachineComputationAlgorithm

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Randomized Algorithms (Spring 2016)

Ryan O'Donnell

July 15, 2017 79 min

★ ★ ★ ★ ★ 5/5

Randomized AlgorithmsTheoretical Computer ScienceMarkov's Inequality

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Random Walks and Markov Chains (Spring 2016)

Ryan O'Donnell

July 15, 2017 79 min

★ ★ ★ ★ ☆ 4/5

Random WalksMarkov ChainsTheoretical Computer Science

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Quantum Computing (Spring 2016)

Ryan O'Donnell

July 15, 2017 77 min

★ ★ ★ ★ ☆ 4/5

Quantum ComputingTheoretical Computer ScienceQubits

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Probability 2 (Spring 2015)

Ryan O'Donnell

July 15, 2017 80 min

★ ★ ★ ★ ★ 5/5

ProbabilityRandom VariablesExpectation

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Probability 1 (Spring 2013)

Ryan O'Donnell

July 15, 2017 65 min

★ ★ ★ ★ ☆ 4/5

ProbabilityRandomized AlgorithmsConditional Probability

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Polynomials (Spring 2015)

Ryan O'Donnell

July 15, 2017 74 min

★ ★ ★ ★ ☆ 4/5

PolynomialsFinite FieldsError Correcting Codes

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: On Proofs (Spring 2016)

Ryan O'Donnell

July 15, 2017 63 min

★ ★ ★ ★ ☆ 4/5

ProofsTheoretical Computer ScienceMathematics

Formal & Physical Sciences Mathematics

Great Ideas in Theoretical Computer Science: Number Theory (Spring 2015)

Ryan O'Donnell

July 15, 2017 80 min

★ ★ ★ ★ ☆ 4/5

Number TheoryAlgorithmsPrimality Testing

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Logic (Spring 2013)

Ryan O'Donnell

July 15, 2017 71 min

★ ★ ★ ★ ☆ 4/5

LogicPropositional LogicFirst-Order Logic

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Linear Algebra (Spring 2016)

Ryan O'Donnell

July 15, 2017 76 min

★ ★ ★ ★ ☆ 4/5

Linear AlgebraTheoretical Computer ScienceFibonacci

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Group Theory (Spring 2016)

Ryan O'Donnell

July 15, 2017 80 min

★ ★ ★ ★ ★ 5/5

Group TheoryTheoretical Computer ScienceLagrange's Theorem

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Graphs: The Basics (Spring 2015)

Ryan O'Donnell

July 15, 2017 79 min

★ ★ ★ ★ ☆ 4/5

Graph TheoryTheoretical Computer ScienceLecture

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Graph Algorithms (Spring 2015)

Ryan O'Donnell

July 15, 2017 70 min

★ ★ ★ ★ ☆ 4/5

Graph AlgorithmsBFSDFS

Formal & Physical Sciences Mathematics

Great Ideas in Theoretical Computer Science: Gödel's Incompleteness Theorems (Spring 2013)

Ryan O'Donnell

July 15, 2017 69 min

★ ★ ★ ★ ☆ 4/5

GödelIncompletenessTuring Machine

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Finite Automata (Spring 2015)

Ryan O'Donnell

July 15, 2017 79 min

★ ★ ★ ★ ★ 5/5

Finite AutomataDFARegular Languages

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Fast Integer Multiplication (Spring 2016)

Ryan O'Donnell

July 15, 2017 74 min

★ ★ ★ ★ ☆ 4/5

Integer MultiplicationFast Fourier TransformSchönhage-Strassen

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Epilogue: Why Max-Cut is My Favorite (Spring 2015)

Ryan O'Donnell

July 15, 2017 61 min

★ ★ ★ ★ ★ 5/5

Max-CutApproximation AlgorithmsSemidefinite Programming

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Deductive Systems (Spring 2015)

Ryan O'Donnell

July 15, 2017 81 min

★ ★ ★ ★ ☆ 4/5

Deductive SystemsPropositional LogicTheoretical Computer Science

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Countability and Diagonalization (Spring 2013)

Ryan O'Donnell

July 15, 2017 73 min

★ ★ ★ ★ ★ 5/5

CountabilityDiagonalizationCantor

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Computability (Spring 2013)

Ryan O'Donnell

July 15, 2017 79 min

★ ★ ★ ★ ★ 5/5

Turing MachineComputabilityDecidability

Formal & Physical Sciences Computing & Cybersecurity

Great Ideas in Theoretical Computer Science: Approximation Algorithms (Spring 2016)

Ryan O'Donnell

July 15, 2017 79 min

★ ★ ★ ★ ☆ 4/5

Approximation AlgorithmsVertex CoverTSP