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 & CybersecurityENGreat Ideas in Theoretical Computer Science: Approximation Algorithms (Spring 2016)Ryan O'DonnellJuly 15, 2017 79 min★ ★ ★ ★ ☆ 4/5Approximation AlgorithmsVertex CoverTSP
Formal & Physical Sciences MathematicsENAnalysis of Boolean Functions at CMU - Lecture 22: Sanders's TheoremRyan O'DonnellJuly 12, 2017 75 min★ ★ ★ ★ ★ 5/5Sanders's TheoremAdditive CombinatoricsFourier Analysis
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 MathematicsENAnalysis of Boolean Functions at CMU - Lecture 21: Additive combinatoricsRyan O'DonnellJuly 8, 2017 82 min★ ★ ★ ★ ☆ 4/5Additive CombinatoricsBoolean FunctionsFourier Analysis
Formal & Physical Sciences MathematicsENAnalysis of Boolean Functions at CMU - Lecture 20: Majority Is Stablest TheoremRyan O'DonnellJuly 8, 2017 76 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisMajority Is Stablest
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 MathematicsENAnalysis of Boolean Functions at CMU - Lecture 18: The Hypercontractivity TheoremRyan O'DonnellJuly 8, 2017 77 min★ ★ ★ ★ ★ 5/5Boolean FunctionsHypercontractivityFourier Analysis
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 MathematicsENAnalysis of Boolean Functions at CMU - Lecture 12: Bonami's Lemma and the KKL TheoremRyan O'DonnellJuly 8, 2017 79 min★ ★ ★ ★ ★ 5/5Analysis of Boolean FunctionsBonami's LemmaKKL Theorem
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
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 7: DNF formulasRyan O'DonnellJuly 7, 2017 75 min★ ★ ★ ★ ★ 5/5Boolean FunctionsDNFFourier Analysis
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 6: Restrictions and the Goldreich--Levin TheoremRyan O'DonnellJuly 7, 2017 81 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisGoldreich-Levin Theorem
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 5: Spectral concentration and learningRyan O'DonnellJuly 7, 2017 80 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisLearning Theory
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 4: Noise stability and Arrow's TheoremRyan O'DonnellJuly 7, 2017 81 min★ ★ ★ ★ ★ 5/5Boolean FunctionsNoise StabilityFourier Analysis
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 3: Social choice and influencesRyan O'DonnellJuly 7, 2017 77 min★ ★ ★ ★ ★ 5/5Boolean FunctionsSocial ChoiceInfluence
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 2: Probability densities and BLR linearity testingRyan O'DonnellJuly 7, 2017 72 min★ ★ ★ ★ ★ 5/5Analysis of Boolean FunctionsFourier AnalysisProbability Densities
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 10: LTFs and noise stabilityRyan O'DonnellJuly 7, 2017 78 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisNoise Stability
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean Functions at CMU - Lecture 1: The Fourier expansion and basic formulasRyan O'DonnellJuly 7, 2017 71 min★ ★ ★ ★ ★ 5/5Boolean FunctionsFourier AnalysisHarmonic Analysis
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 23: The Polynomial HierarchyAnil AdaJuly 3, 2017 77 min★ ★ ★ ★ ☆ 4/5Complexity TheoryPolynomial HierarchyNP
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 22: BPPVenkatesan GuruswamiJuly 3, 2017 79 min★ ★ ★ ★ ★ 5/5BPPRandomized AlgorithmsComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 21: Randomized Complexity: RP, coRP, and ZPPRyan O'DonnellJuly 3, 2017 81 min★ ★ ★ ★ ☆ 4/5Randomized AlgorithmsComplexity ClassesRP
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 20: The Immerman--Szelepcsényi TheoremRyan O'DonnellJuly 3, 2017 81 min★ ★ ★ ★ ★ 5/5Complexity TheoryImmerman-SzelepcsényiNL=coNL
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 19: From P-Completeness to PSPACE-CompletenessRyan O'DonnellJuly 3, 2017 79 min★ ★ ★ ★ ★ 5/5Complexity TheoryP-CompletenessPSPACE-Completeness
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 18: NL-Completeness and Logspace ReductionsRyan O'DonnellJuly 3, 2017 80 min★ ★ ★ ★ ★ 5/5Computational ComplexityNL-CompletenessLogspace Reductions
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 17: Savitch's Theorem and NLRyan O'DonnellJuly 3, 2017 81 min★ ★ ★ ★ ★ 5/5Complexity TheorySavitch's TheoremNL
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 16: Space ComplexityRyan O'DonnellJuly 3, 2017 81 min★ ★ ★ ★ ★ 5/5Space ComplexityTuring MachinesComplexity Classes
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 15: coNPRyan O'DonnellJuly 3, 2017 81 min★ ★ ★ ★ ★ 5/5CoNPComplexity TheoryNP
Formal & Physical Sciences Computing & CybersecurityENUndergrad Complexity at CMU - Lecture 9: NondeterminismRyan O'DonnellJune 24, 2017 81 min★ ★ ★ ★ ☆ 4/5NondeterminismComplexity TheoryNP
