Graph Theory Courses

Ryan O'Donnell

Dinur's PCP- Degree-Reduction, Expanderizing, Mini-PCP - Lecture 27c of CS Theory Toolkit

Explore Dinur's PCP Theorem proof, covering degree-reduction, expanderizing, and alphabet-reduction in theoretical computer science. Gain insights into advanced concepts for research in computational complexity.

• YouTube
• 26 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Deterministic Communication Complexity - Lecture 23b of CS Theory Toolkit

Explore deterministic communication complexity, protocols, matrices, and the Log Rank conjecture in this graduate-level lecture on theoretical computer science fundamentals.

• YouTube
• 37 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Trees and Series-Parallel Graphs - Lecture 22a of CS Theory Toolkit

Explore treewidth, CSPs, and graph theory fundamentals for theoretical computer science research, focusing on trees and series-parallel graphs.

• YouTube
• 21 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Goemans-Williamson: Rounding the Max-Cut SDP - Lecture 20a of CS Theory Toolkit

Efficient algorithm for approximating maximum graph cuts using semidefinite programming and randomized rounding, with guaranteed performance ratio of 0.878.

• YouTube
• 32 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

The SDP Relaxation for Max-Cut - Lecture 19b of CS Theory Toolkit

Explore SDP relaxation for Max-Cut, transforming a quadratic program into a semidefinite program solvable by the Ellipsoid Algorithm. Part of CMU's graduate-level CS Theory Toolkit course.

• YouTube
• 33 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

The Ellipsoid Algorithm - Lecture 19a of CS Theory Toolkit

Explore the Ellipsoid Algorithm for solving Linear Programming and convex optimization, focusing on its polynomial-time efficiency and use of separation oracles in theoretical computer science.

• YouTube
• 31 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Linear Programming - Bit Complexity - Lecture 17c of CS Theory Toolkit

Explore bit complexity in Linear Programming, feasible solutions, and the implications for NP ∩ coNP. Delve into fundamental concepts for theoretical computer science research.

• YouTube
• 25 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Linear Programming Duality - Lecture 17b of CS Theory Toolkit

Explore linear programming duality, Farkas Lemma, and Fourier-Motzkin elimination in this graduate-level lecture on fundamental concepts for theoretical computer science research.

• YouTube
• 22 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Expander Graph Constructions - Lecture of CS Theory Toolkit

Explore explicit expander graph constructions, including Gabber-Galil, Ramanujan, and Zig-Zag product expanders. Learn about their properties, applications, and mathematical foundations in theoretical computer science.

• YouTube
• 49 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Linear Error Correcting Codes - Lecture 11b of CS Theory Toolkit

Explore linear error correcting codes, their properties, and applications in computer science theory. Learn about decoding, notation, and minimum distance in this graduate-level lecture.

• YouTube
• 20 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Fourier Analysis of Boolean Functions - Lecture 8a of CS Theory Toolkit

Explore Fourier analysis of Boolean functions, focusing on real-valued functions and their Fourier transforms in this graduate-level theoretical computer science lecture.

• YouTube
• 32 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Fast Fourier Transform - Lecture 7c of CS Theory Toolkit

Explore the Fast Fourier Transform algorithm and its application in efficient integer multiplication, with insights from a CMU graduate-level computer science theory course.

• YouTube
• 26 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

The Word RAM Model - Lecture 6c of CS Theory Toolkit

Explore the Word RAM model for algorithms and its impact on integer sorting complexity in this graduate-level lecture on theoretical computer science fundamentals.

• YouTube
• 26 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Factorial Asymptotics, Stirling's Formula - Lecture 3b of CS Theory Toolkit

Explore factorial asymptotics and Stirling's Formula in this graduate-level lecture, covering mathematical techniques for theoretical computer science research.

• YouTube
• 28 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Big O and Friends - Lecture 2a of CS Theory Toolkit

Explore asymptotic notation in theoretical computer science, covering Big O, Omega, and related concepts. Essential for understanding algorithm efficiency and complexity analysis.

• YouTube
• 28 minutes
• Self-Paced
• Free Video