Formal & Physical Sciences Computing & CybersecurityENComputational Indistinguishability || @ CMU || Lecture 25b of CS Theory ToolkitRyan O'DonnellJuly 9, 2020 13 min★ ★ ★ ★ ☆ 4/5Computational IndistinguishabilityHybrid ArgumentCryptography
Formal & Physical Sciences Computing & CybersecurityENInformation Complexity || @ CMU || Lecture 24c of CS Theory ToolkitRyan O'DonnellJuly 7, 2020 28 min★ ★ ★ ★ ☆ 4/5Information ComplexityCommunication ComplexityMutual Information
Formal & Physical Sciences Computing & CybersecurityENYao's Minimax Theorem & IP_2's Communication Complexity || @ CMU || Lecture 23d of CS Theory ToolkitRyan O'DonnellJuly 2, 2020 19 min★ ★ ★ ★ ★ 5/5Communication ComplexityYao's Minimax TheoremFourier Analysis
Formal & Physical Sciences Computing & CybersecurityENRandomized Communication Complexity || @ CMU || Lecture 23c of CS Theory ToolkitRyan O'DonnellJuly 1, 2020 13 min★ ★ ★ ★ ★ 5/5Communication ComplexityRandomized AlgorithmsPublic Coins
Formal & Physical Sciences Computing & CybersecurityENDeterministic Communication Complexity || @ CMU || Lecture 23b of CS Theory ToolkitRyan O'DonnellJune 30, 2020 37 min★ ★ ★ ★ ★ 5/5Communication ComplexityDeterministic ProtocolsCombinatorial Rectangles
Formal & Physical Sciences Computing & CybersecurityENBasics of Communication Complexity || @ CMU || Lecture 23a of CS Theory ToolkitRyan O'DonnellJune 29, 2020 19 min★ ★ ★ ★ ★ 5/5Communication ComplexityTheory of ComputationLower Bounds
Formal & Physical Sciences Computing & CybersecurityENGreat Ideas in Theoretical Computer Science: Introduction (Spring 2016) reupload with improved audioRyan O'DonnellJune 28, 2020 72 min★ ★ ★ ★ ★ 5/5Theoretical Computer ScienceAlgorithmsComputation
Formal & Physical Sciences Computing & CybersecurityENTreewidth Definitions || @ CMU || Lecture 22b of CS Theory ToolkitRyan O'DonnellJune 25, 2020 32 min★ ★ ★ ★ ★ 5/5TreewidthGraph TheoryTheoretical Computer Science
Formal & Physical Sciences Computing & CybersecurityENPseudoexpectations || @ CMU || Lecture 21(d) of CS Theory ToolkitRyan O'DonnellJune 23, 2020 13 min★ ★ ★ ★ ☆ 4/5PseudoexpectationsSherali-AdamsSOS
Formal & Physical Sciences Computing & CybersecurityENThe Sum-of-Squares (SOS) Proof System || @ CMU || Lecture 21(c) of CS Theory ToolkitRyan O'DonnellJune 22, 2020 22 min★ ★ ★ ★ ☆ 4/5Sum-of-SquaresProof SystemsSemidefinite Programming
Formal & Physical Sciences Computing & CybersecurityENProof Complexity for CSPs || @ CMU || Lecture 21a of CS Theory ToolkitRyan O'DonnellJune 18, 2020 12 min★ ★ ★ ★ ☆ 4/5Proof ComplexityConstraint SatisfactionLinear Programming
Formal & Physical Sciences Computing & CybersecurityENCSP Approximability: Optimization and Certification || @ CMU || Lecture 20c of CS Theory ToolkitRyan O'DonnellJune 17, 2020 33 min★ ★ ★ ★ ★ 5/5CSPApproximation AlgorithmsCertification
Formal & Physical Sciences Computing & CybersecurityENConstraint Satisfaction Problems || @ CMU || Lecture 20b of CS Theory ToolkitRyan O'DonnellJune 16, 2020 31 min★ ★ ★ ★ ★ 5/5Constraint Satisfaction ProblemsDichotomy TheoremTheoretical Computer Science
Formal & Physical Sciences Computing & CybersecurityENGoemans--Williamson: Rounding the Max-Cut SDP || @ CMU || Lecture 20a of CS Theory ToolkitRyan O'DonnellJune 15, 2020 31 min★ ★ ★ ★ ★ 5/5Max-CutSDPGoemans-Williamson
Formal & Physical Sciences Computing & CybersecurityENThe SDP Relaxation for Max-Cut || @ CMU || Lecture 19b of CS Theory ToolkitRyan O'DonnellJune 11, 2020 33 min★ ★ ★ ★ ★ 5/5SDPMax-CutSemidefinite Programming
Formal & Physical Sciences Computing & CybersecurityENMin-st-Cut is the dual LP of Max-st-Flow || @ CMU || Lecture 18d of CS Theory ToolkitRyan O'DonnellJune 9, 2020 19 min★ ★ ★ ★ ★ 5/5Linear ProgrammingMax-Flow Min-CutDuality
Formal & Physical Sciences Computing & CybersecurityENRounding LP Solutions: Min-Vertex-Cover || @ CMU || Lecture 18c of CS Theory ToolkitRyan O'DonnellJune 8, 2020 17 min★ ★ ★ ★ ☆ 4/5Linear ProgrammingVertex CoverApproximation Algorithms
Formal & Physical Sciences Computing & CybersecurityENRelaxing ILPs to LPs: Bipartite Max-Perfect-Matching || @ CMU || Lecture 18b of CS Theory ToolkitRyan O'DonnellJune 5, 2020 28 min★ ★ ★ ★ ★ 5/5Linear ProgrammingInteger Linear ProgrammingBipartite Matching
Formal & Physical Sciences Computing & CybersecurityENExpander Graph Application 2: Derandomization || @ CMU || Lecture 16c of CS Theory ToolkitRyan O'DonnellMay 4, 2020 22 min★ ★ ★ ★ ★ 5/5Expander GraphsDerandomizationRandomized Algorithms
Formal & Physical Sciences Computing & CybersecurityENCheeger's Inequality || @ CMU || Lecture 15d of CS Theory ToolkitRyan O'DonnellMay 3, 2020 61 min★ ★ ★ ★ ★ 5/5Cheeger's InequalitySpectral Graph TheoryLaplacian Eigenvalues
Formal & Physical Sciences Computing & CybersecurityENEpsilon-biased Generators || @ CMU || Lecture 12d of CS Theory ToolkitRyan O'DonnellApril 23, 2020 23 min★ ★ ★ ★ ★ 5/5Epsilon-Biased GeneratorsPseudorandomnessCoding Theory
Formal & Physical Sciences Computing & CybersecurityENImpagliazzo--Wigderson, and Nisan's PRGs || @ CMU || Lecture 12b of CS Theory ToolkitRyan O'DonnellApril 21, 2020 12 min★ ★ ★ ★ ☆ 4/5PseudorandomnessComplexity TheoryDerandomization
Formal & Physical Sciences Computing & CybersecurityENPseudorandom Generators || @ CMU || Lecture 12a of CS Theory ToolkitRyan O'DonnellApril 20, 2020 20 min★ ★ ★ ★ ☆ 4/5Pseudorandom GeneratorsComplexity TheoryBPP
Formal & Physical Sciences Computing & CybersecurityENCQC2T Colloquium/QSI Seminar: Prof Zhengfeng Ji, QSI, Spooky Complexity at a Distance, 26/03/2020Zhengfeng JiApril 20, 2020 77 min★ ★ ★ ★ ★ 5/5Quantum ComplexityMIP*Interactive Proofs
Formal & Physical Sciences Computing & CybersecurityENMultivariate Polynomials and the Schwartz--Zippel Lemma || @ CMU || Lecture 10e of CS Theory ToolkitRyan O'DonnellMarch 28, 2020 18 min★ ★ ★ ★ ★ 5/5Schwartz-ZippelMultivariate PolynomialsFinite Fields
Formal & Physical Sciences Computing & CybersecurityENCommunication Complexity of Equality || @ CMU || Lecture 10d of CS Theory ToolkitRyan O'DonnellMarch 27, 2020 15 min★ ★ ★ ★ ★ 5/5Communication ComplexityPolynomialsFinite Fields
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
