Computing & Cybersecurity

3003 tuit · page 74/76

Formal & Physical Sciences Computing & Cybersecurity

Probabilistic Complexity Classes: Graduate Complexity Lecture 5 at CMU

Ryan O'Donnell

September 19, 2017 80 min

★ ★ ★ ★ ★ 5/5

Complexity TheoryProbabilistic Turing MachinesBPP

Formal & Physical Sciences Computing & Cybersecurity

Hopcroft--Paul--Valiant Theorem: Graduate Complexity Lecture 3 at CMU

Ryan O'Donnell

September 18, 2017 80 min

★ ★ ★ ★ ★ 5/5

Complexity TheorySpace ComplexityTime Complexity

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 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 Computing & Cybersecurity

Spring 2013 Lecture 19 Quantum Computation

Ryan O'Donnell

July 15, 2017 79 min

★ ★ ★ ★ ☆ 4/5

Quantum ComputationReversible CircuitsProbabilistic Circuits

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

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 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 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

Formal & Physical Sciences Computing & Cybersecurity

Analysis of Boolean Functions at CMU - Lecture 23: Open problems

Ryan O'Donnell

July 8, 2017 76 min

★ ★ ★ ★ ★ 5/5

Boolean FunctionsFourier AnalysisOpen Problems

Formal & Physical Sciences Computing & Cybersecurity

Analysis of Boolean Functions at CMU - Lecture 19: Invariance theorems

Ryan O'Donnell

July 8, 2017 77 min

★ ★ ★ ★ ★ 5/5

Boolean FunctionsInvariance PrincipleCentral Limit Theorem

Formal & Physical Sciences Computing & Cybersecurity

Analysis of Boolean Functions at CMU - Lecture 17: UG-hardness results from dictator tests

John Wright

July 8, 2017 84 min

★ ★ ★ ★ ☆ 4/5

Unique Games ConjectureDictator TestingHardness of Approximation

Formal & Physical Sciences Computing & Cybersecurity

Analysis of Boolean Functions at CMU - Lecture 16: Håstad's hardness theorems

Ryan O'Donnell

July 8, 2017 78 min

★ ★ ★ ★ ★ 5/5

Boolean FunctionsFourier AnalysisHardness of Approximation

Formal & Physical Sciences Computing & Cybersecurity

Analysis of Boolean Functions at CMU - Lecture 15: Constraint satisfacation problems

Ryan O'Donnell

July 8, 2017 75 min

★ ★ ★ ★ ★ 5/5

Constraint SatisfactionBoolean FunctionsHardness of Approximation

Formal & Physical Sciences Computing & Cybersecurity

Analysis of Boolean Functions at CMU - Lecture 14: Probabilistically checkable proofs of proximity

Ryan O'Donnell

July 8, 2017 76 min

★ ★ ★ ★ ★ 5/5

PCPProperty TestingBoolean Functions

Formal & Physical Sciences Computing & Cybersecurity

Analysis of Boolean Functions at CMU - Lecture 13: Dictator Testing and the FKN Theorem

Ryan O'Donnell

July 8, 2017 77 min

★ ★ ★ ★ ★ 5/5

Boolean FunctionsFourier AnalysisProperty Testing