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 MathematicsENSolving the Max-Cut SDP || @ CMU || Lecture 19c of CS Theory ToolkitRyan O'DonnellJune 12, 2020 15 min★ ★ ★ ★ ☆ 4/5Max-CutSemidefinite ProgrammingEllipsoid Method
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 MathematicsENThe Ellipsoid Algorithm || @ CMU || Lecture 19a of CS Theory ToolkitRyan O'DonnellJune 10, 2020 30 min★ ★ ★ ★ ☆ 4/5Ellipsoid AlgorithmLinear ProgrammingConvex Optimization
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 MathematicsENMax-st-Flow is an LP || @ CMU || Lecture 18a of CS Theory ToolkitRyan O'DonnellJune 4, 2020 14 min★ ★ ★ ★ ☆ 4/5Linear ProgrammingMax FlowCombinatorial Optimization
Formal & Physical Sciences MathematicsENLinear Programming: Optimization Reduces to Feasibility || @ CMU || Lecture 17d of CS Theory ToolkitRyan O'DonnellJune 3, 2020 22 min★ ★ ★ ★ ★ 5/5Linear ProgrammingOptimizationFeasibility
Formal & Physical Sciences MathematicsENLinear Programming: Bit Complexity || @ CMU || Lecture 17c of CS Theory ToolkitRyan O'DonnellJune 2, 2020 24 min★ ★ ★ ★ ★ 5/5Linear ProgrammingBit ComplexityNP
Formal & Physical Sciences MathematicsENLinear Programming Duality || @ CMU || Lecture 17b of CS Theory ToolkitRyan O'DonnellJune 1, 2020 22 min★ ★ ★ ★ ☆ 4/5Linear ProgrammingDualityFarkas Lemma
Formal & Physical Sciences MathematicsENLinear Programming: Definitions || @ CMU || Lecture 17a of CS Theory ToolkitRyan O'DonnellMay 29, 2020 10 min★ ★ ★ ★ ☆ 4/5Linear ProgrammingOptimizationPolynomial Time
Formal & Physical Sciences MathematicsENExpander Graphs Overview || @ CMU || Lecture 16a of CS Theory ToolkitRyan O'DonnellMay 4, 2020 28 min★ ★ ★ ★ ★ 5/5Expander GraphsGraph TheorySpectral Graph Theory
Formal & Physical Sciences MathematicsENExpander Graphs Application 1: Good Codes || @ CMU || Lecture 16b of CS Theory ToolkitRyan O'DonnellMay 4, 2020 26 min★ ★ ★ ★ ★ 5/5Expander GraphsError-Correcting CodesLinear Codes
Formal & Physical Sciences MathematicsENExpander Graph Constructions || @ CMU || Lecture 16d of CS Theory ToolkitRyan O'DonnellMay 4, 2020 48 min★ ★ ★ ★ ☆ 4/5Expander GraphsSpectral Graph TheoryRamanujan Graphs
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 MathematicsENSpectral Graph Theory: mixing time || @ CMU || Lecture 15c of CS Theory ToolkitRyan O'DonnellMay 2, 2020 39 min★ ★ ★ ★ ☆ 4/5Spectral Graph TheoryMixing TimeRandom Walk
Formal & Physical Sciences MathematicsENSpectral Graph Theory: conductance and Sparsest-Cut || @ CMU || Lecture 15b of CS Theory ToolkitRyan O'DonnellMay 1, 2020 18 min★ ★ ★ ★ ☆ 4/5Spectral Graph TheoryConductanceSparsest-Cut
Formal & Physical Sciences MathematicsENSpectral Graph Theory: eigenvalues || @ CMU || Lecture 15a of CS Theory ToolkitRyan O'DonnellApril 30, 2020 22 min★ ★ ★ ★ ☆ 4/5Spectral Graph TheoryEigenvaluesRandom Walks
Formal & Physical Sciences MathematicsENSpectral Graph Theory: the Laplacian, and the Spectral Theorem || @ CMU || 14b of CS Theory ToolkitRyan O'DonnellApril 29, 2020 37 min★ ★ ★ ★ ☆ 4/5Spectral Graph TheoryLaplacianEigenvalues
Formal & Physical Sciences MathematicsENSpectral Graph Theory: the Markov transition operator || @ CMU || Lecture 14a of CS Theory ToolkitRyan O'DonnellApril 28, 2020 41 min★ ★ ★ ★ ★ 5/5Spectral Graph TheoryMarkov ChainLinear Algebra
Formal & Physical Sciences MathematicsENSpectral Graph Theory: Minimizing/Maximizing the Quadratic Form || @ CMU || 13d of CS Theory ToolkitRyan O'DonnellApril 27, 2020 33 min★ ★ ★ ★ ☆ 4/5Spectral Graph TheoryQuadratic FormEigenvalues
Formal & Physical Sciences MathematicsENSpectral Graph Theory: Enter Linear Algebra || @ CMU || Lecture 13c of CS Theory ToolkitRyan O'DonnellApril 26, 2020 20 min★ ★ ★ ★ ☆ 4/5Spectral Graph TheoryLinear AlgebraRandom Walks
Formal & Physical Sciences MathematicsENSpectral Graph Theory: The Standard Random Walk || @ CMU || Lecture 13b of CS Theory ToolkitRyan O'DonnellApril 25, 2020 24 min★ ★ ★ ★ ★ 5/5Spectral Graph TheoryRandom WalkStationary Distribution
Formal & Physical Sciences MathematicsENSpectral Graph Theory: The Quadratic Form || @ CMU || Lecture 13a of CS Theory ToolkitRyan O'DonnellApril 24, 2020 22 min★ ★ ★ ★ ★ 5/5Spectral Graph TheoryQuadratic FormGraph Laplacian
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 & CybersecurityENk-wise Independent Generators || @ CMU || Lecture 12c of CS Theory ToolkitRyan O'DonnellApril 22, 2020 26 min★ ★ ★ ★ ★ 5/5PseudorandomnessK-Wise IndependenceError-Correcting Codes
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 Science — General & HistoryENAsymptotically "Good" Codes || @ CMU || Lecture 11e of CS Theory ToolkitRyan O'DonnellApril 9, 2020 10 min★ ★ ★ ★ ☆ 4/5Error-Correcting CodesCoding TheoryAsymptotic Rate
Formal & Physical Sciences Science — General & HistoryENReed--Solomon Codes || @ CMU || Lecture 11d of CS Theory ToolkitRyan O'DonnellApril 8, 2020 12 min★ ★ ★ ★ ☆ 4/5Reed-SolomonError-Correcting CodesPolynomials
Formal & Physical Sciences Science — General & HistoryENHamming Code and Hadamard Code || @ CMU || Lecture 11c of CS Theory ToolkitRyan O'DonnellApril 7, 2020 21 min★ ★ ★ ★ ☆ 4/5Coding TheoryHamming CodeHadamard Code
Formal & Physical Sciences Science — General & HistoryENLinear Error Correcting Codes || @ CMU || Lecture 11b of CS Theory ToolkitRyan O'DonnellApril 6, 2020 20 min★ ★ ★ ★ ☆ 4/5Coding TheoryLinear CodesError Correction
Formal & Physical Sciences Science — General & HistoryENError Correcting Codes || @ CMU || Lecture 11a of CS Theory ToolkitRyan O'DonnellMarch 31, 2020 16 min★ ★ ★ ★ ☆ 4/5Error Correcting CodesHamming DistanceCoding Theory
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 MathematicsENNon-Prime Fields || @ CMU || Lecture 10c of CS Theory ToolkitRyan O'DonnellMarch 25, 2020 20 min★ ★ ★ ★ ☆ 4/5Finite FieldsPolynomialsIrreducible Polynomials
