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 & 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 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 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 & 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 & 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 & CybersecurityENSimon's Algorithm: Lecture 13 of Quantum Computation at CMURyan O'DonnellOctober 23, 2018 81 min★ ★ ★ ★ ★ 5/5Simon's AlgorithmQuantum ComputingFourier Sampling
Formal & Physical Sciences Computing & CybersecurityENRevealing XOR-patterns I: Lecture 11 of Quantum Computation at CMURyan O'DonnellOctober 14, 2018 83 min★ ★ ★ ★ ★ 5/5Quantum ComputingXORHadamard Transform
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
![Razborov--Smolensky lower bounds for AC0[p]: Graduate Complexity Lecture 22 at CMU](https://i.ytimg.com/vi/TI-xKI3Uy4E/maxresdefault.jpg)
