Formal & Physical Sciences MathematicsENPrimes and Prime Fields || @ CMU || Lecture 10b of CS Theory ToolkitRyan O'DonnellMarch 24, 2020 16 min★ ★ ★ ★ ★ 5/5Prime FieldsFinite FieldsEuclid's Algorithm
Formal & Physical Sciences MathematicsENExpander Graphs (full lecture) || @ CMU || Lecture 16 of CS Theory ToolkitRyan O'DonnellMarch 19, 2020 125 min★ ★ ★ ★ ★ 5/5Expander GraphsSpectral Graph TheoryError-Correcting Codes
Formal & Physical Sciences Computing & CybersecurityENGrover's Algorithm || @ CMU || Lecture 9c of CS Theory ToolkitRyan O'DonnellMarch 15, 2020 23 min★ ★ ★ ★ ★ 5/5Quantum ComputingGrover's AlgorithmTheoretical Computer Science
Formal & Physical Sciences Computing & CybersecurityENAxioms of Quantum Computing || @ CMU || Lecture 9b of CS Theory ToolkitRyan O'DonnellMarch 14, 2020 40 min★ ★ ★ ★ ☆ 4/5Quantum ComputingQuantum MechanicsAxioms
Formal & Physical Sciences Computing & CybersecurityENQuantum Computing Overview || @ CMU || Lecture 9a of CS Theory ToolkitRyan O'DonnellMarch 13, 2020 14 min★ ★ ★ ★ ☆ 4/5Quantum ComputingFourier TransformShor's Algorithm
Formal & Physical Sciences Computing & CybersecurityENAnalysis of Boolean functions: Applications || @ CMU || Lecture 8c of CS Theory ToolkitRyan O'DonnellMarch 12, 2020 13 min★ ★ ★ ★ ☆ 4/5Boolean FunctionsFourier AnalysisSocial Choice
Formal & Physical Sciences Computing & CybersecurityENBoolean Fourier formulas || @ CMU || Lecture 8b of CS Theory ToolkitRyan O'DonnellMarch 11, 2020 34 min★ ★ ★ ★ ★ 5/5Boolean Fourier AnalysisWalsh-Hadamard TransformParseval's Identity
Formal & Physical Sciences Computing & CybersecurityENFourier Analysis of Boolean functions || @ CMU || Lecture 8a of CS Theory ToolkitRyan O'DonnellMarch 10, 2020 32 min★ ★ ★ ★ ★ 5/5Fourier AnalysisBoolean FunctionsTheoretical Computer Science
Formal & Physical Sciences Computing & CybersecurityENFast Fourier Transform (FFT) || @ CMU || Lecture 7c of CS Theory ToolkitRyan O'DonnellMarch 9, 2020 25 min★ ★ ★ ★ ★ 5/5Fast Fourier TransformDiscrete Fourier TransformInteger Multiplication
Formal & Physical Sciences Computing & CybersecurityENMultiplication via the DFT || @ CMU || Lecture 7b of CS Theory ToolkitRyan O'DonnellMarch 6, 2020 26 min★ ★ ★ ★ ★ 5/5DFTFFTPolynomial Multiplication
Formal & Physical Sciences Computing & CybersecurityENComplexity of Basic Arithmetic || @ CMU || Lecture 7a of CS Theory ToolkitRyan O'DonnellMarch 5, 2020 26 min★ ★ ★ ★ ☆ 4/5Integer MultiplicationFFTComplexity Theory
Formal & Physical Sciences Computing & CybersecurityENThe Word RAM Model || @ CMU || Lecture 6c of CS Theory ToolkitRyan O'DonnellMarch 4, 2020 25 min★ ★ ★ ★ ★ 5/5Word RAMSortingAlgorithms
Formal & Physical Sciences Computing & CybersecurityENComputational Models: Circuits || @ CMU || Lecture 6b of CS Theory ToolkitRyan O'DonnellMarch 3, 2020 29 min★ ★ ★ ★ ★ 5/5Boolean CircuitsComplexity ClassesCircuit Lower Bounds
Formal & Physical Sciences Computing & CybersecurityENComputational Models: Turing Machines || @ CMU || Lecture 6a of CS Theory ToolkitRyan O'DonnellMarch 2, 2020 25 min★ ★ ★ ★ ★ 5/5Turing MachineComputational ModelsComplexity Theory
Formal & Physical Sciences MathematicsENChernoff, Hoeffding, etc. bounds || @ CMU || Lecture 5c of CS Theory ToolkitRyan O'DonnellFebruary 18, 2020 17 min★ ★ ★ ★ ★ 5/5Chernoff BoundHoeffding BoundConcentration Inequalities
Formal & Physical Sciences MathematicsENProof of the Chernoff Bound || @ CMU || Lecture 5b of CS Theory ToolkitRyan O'DonnellFebruary 17, 2020 24 min★ ★ ★ ★ ★ 5/5Chernoff BoundProbability TheoryConcentration Inequalities
Formal & Physical Sciences MathematicsENMarkov and Chebyshev Inequalities || @ CMU || Lecture 5a of CS Theory ToolkitRyan O'DonnellFebruary 14, 2020 38 min★ ★ ★ ★ ★ 5/5Markov InequalityChebyshev InequalityProbability Bounds
Formal & Physical Sciences MathematicsENBerry--Esseen Theorem || @ CMU || Lecture 4c of CS Theory ToolkitRyan O'DonnellFebruary 13, 2020 16 min★ ★ ★ ★ ★ 5/5Berry-Esseen TheoremCentral Limit TheoremProbability Theory
Formal & Physical Sciences MathematicsENGaussian Random Variables || @ CMU || Lecture 4b of CS Theory ToolkitRyan O'DonnellFebruary 12, 2020 38 min★ ★ ★ ★ ★ 5/5GaussianProbabilityCentral Limit Theorem
Formal & Physical Sciences MathematicsENCentral Limit Theorem || @ CMU || Lecture 4a of CS Theory ToolkitRyan O'DonnellFebruary 11, 2020 24 min★ ★ ★ ★ ★ 5/5Central Limit TheoremProbability TheoryVariance
Formal & Physical Sciences MathematicsENBinomial Coefficients Asymptotics || @ CMU || Lecture 3c of CS Theory ToolkitRyan O'DonnellFebruary 10, 2020 35 min★ ★ ★ ★ ★ 5/5Binomial CoefficientsAsymptoticsEntropy
Formal & Physical Sciences MathematicsENFactorial Asymptotics, Stirling's Formula || @ CMU || Lecture 3b of CS Theory ToolkitRyan O'DonnellFebruary 7, 2020 28 min★ ★ ★ ★ ★ 5/5AsymptoticsStirling's FormulaFactorial
Formal & Physical Sciences MathematicsENBirthday Paradox Asymptotics || @ CMU || Lecture 3a of CS Theory ToolkitRyan O'DonnellFebruary 6, 2020 18 min★ ★ ★ ★ ★ 5/5Birthday ParadoxAsymptoticsProbability
Formal & Physical Sciences Computing & CybersecurityENAsymptotics Tricks || @ CMU || Lecture 2c of CS Theory ToolkitRyan O'DonnellFebruary 5, 2020 25 min★ ★ ★ ★ ☆ 4/5AsymptoticsApproximationTaylor Series
Formal & Physical Sciences MathematicsENHarmonic Numbers Asymptotics || @ CMU || Lecture 2b of CS Theory ToolkitRyan O'DonnellFebruary 4, 2020 22 min★ ★ ★ ★ ☆ 4/5Harmonic NumbersAsymptoticsBig-O Notation
Formal & Physical Sciences Computing & CybersecurityENBig O and friends || @ CMU || Lecture 2a of CS Theory ToolkitRyan O'DonnellFebruary 3, 2020 28 min★ ★ ★ ★ ★ 5/5Asymptotic NotationBig OComplexity Theory
Formal & Physical Sciences MathematicsENStreet Fighting Mathematics || @ CMU || Lecture 1c of TCS ToolkitRyan O'DonnellJanuary 22, 2020 26 min★ ★ ★ ★ ☆ 4/5MathematicsResearch MethodsProblem Solving
Formal & Physical Sciences Computing & CybersecurityENHow to do CS Theory || @ CMU || Lecture 1b of CS Theory ToolkitRyan O'DonnellJanuary 22, 2020 35 min★ ★ ★ ★ ☆ 4/5Theoretical Computer ScienceResearch MethodologyLaTeX
Formal & Physical Sciences Computing & CybersecurityENCS Theory Toolkit: Course Outline || @ CMU || Lecture 1aRyan O'DonnellJanuary 22, 2020 10 min★ ★ ★ ★ ☆ 4/5Theoretical Computer ScienceCourse OutlineAlgorithms
Formal & Physical Sciences MathematicsENExplicit near-Ramanujan graphs of every degreeRyan O'DonnellJuly 9, 2019 55 min★ ★ ★ ★ ☆ 4/5Ramanujan GraphsExpander GraphsSpectral Graph Theory
Formal & Physical Sciences Computing & CybersecurityENQuantum "Supremacy": Lecture 25 of Quantum Computation at CMURyan O'DonnellDecember 7, 2018 81 min★ ★ ★ ★ ☆ 4/5Quantum ComputingQuantum SupremacyFault Tolerance
Formal & Physical Sciences Computing & CybersecurityENQuantum Complexity: Lecture 24 of Quantum Computation at CMURyan O'DonnellDecember 6, 2018 82 min★ ★ ★ ★ ★ 5/5Quantum ComplexityBQPComplexity Classes
Formal & Physical Sciences PhysicsENQuantum Information Theory: Lecture 23 of Quantum Computation at CMURyan O'DonnellDecember 2, 2018 84 min★ ★ ★ ★ ★ 5/5Quantum InformationVon Neumann EntropyHolevo's Bound
Formal & Physical Sciences Computing & CybersecurityENQuantum Probability: Lecture 22 of Quantum Computation at CMURyan O'DonnellNovember 29, 2018 77 min★ ★ ★ ★ ★ 5/5Quantum ProbabilityDensity MatricesQuantum Computation
Formal & Physical Sciences Computing & CybersecurityENThe Adversary Method: Lecture 20 of Quantum Computation at CMURyan O'DonnellNovember 26, 2018 60 min★ ★ ★ ★ ★ 5/5Quantum ComputingQuery ComplexityAdversary Method
Formal & Physical Sciences Computing & CybersecurityENMixed States and Density Matrices: Lecture 21 of Quantum Computation at CMURyan O'DonnellNovember 26, 2018 80 min★ ★ ★ ★ ★ 5/5Quantum ComputationDensity MatricesMixed States
Formal & Physical Sciences Computing & CybersecurityENQuantum Query Complexity: Lecture 19 of Quantum Computation at CMURyan O'DonnellNovember 19, 2018 81 min★ ★ ★ ★ ☆ 4/5Quantum ComputingQuery ComplexityOracle Model
Formal & Physical Sciences Computing & CybersecurityENGrover's Algorithm: Lecture 18 of Quantum Computation at CMURyan O'DonnellNovember 18, 2018 82 min★ ★ ★ ★ ★ 5/5Grover's AlgorithmQuantum ComputingQuantum Query Complexity
Formal & Physical Sciences Computing & CybersecurityENThe Hidden Subgroup Problem: Lecture 17 of Quantum Computation at CMURyan O'DonnellNovember 3, 2018 83 min★ ★ ★ ★ ★ 5/5Quantum ComputingHidden Subgroup ProblemGroup Theory
Formal & Physical Sciences Computing & CybersecurityENShor's Factoring Algorithm: Lecture 16 of Quantum Computation at CMURyan O'DonnellNovember 2, 2018 80 min★ ★ ★ ★ ★ 5/5Shor's AlgorithmQuantum ComputingFactoring
