Theoretical Computer Science Courses and Certifications

Paul G. Allen School

Money, Circuits, Mythic Figures, and More - Theory in the Allen School

Diverse theoretical computer science research: algorithms, data structures, complexity, combinatorics, and economics. Insights from UW Allen School's theory group on cutting-edge topics.

• YouTube
• 53 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Great Ideas in Theoretical Computer Science: Deductive Systems

Explore deductive systems in theoretical computer science, covering topics like Hilbert's 10th problem, binary trees, propositional logic, and logical equivalence.

• YouTube
• 1 hour 22 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Great Ideas in Theoretical Computer Science - On Proofs

Explore theoretical computer science concepts, focusing on proofs: their history, significance, and modern developments. Learn tips for constructing proofs and avoiding common mistakes in mathematical reasoning.

• YouTube
• 1 hour 3 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Analysis of Boolean Functions at CMU - Additive Combinatorics

Explore additive combinatorics in Boolean functions, covering subspaces, cosets, Hamming balls, and the Fryman region conjecture. Gain insights into advanced theoretical concepts.

• YouTube
• 1 hour 22 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Analysis of Boolean Functions - Restrictions and the Goldreich-Levin Theorem

Explore restrictions and the Goldreich-Levin Theorem in Boolean function analysis, covering key concepts, proofs, and applications in this advanced computer science lecture.

• YouTube
• 1 hour 21 minutes
• On-Demand
• Free Video

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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• Free Video

Ryan O'Donnell

How to Do CS Theory - Lecture 1b: Research Tips for Theoretical Computer Science

Insights and tips for aspiring theoretical computer science researchers, covering research methods, paper writing, presentation skills, and essential resources in the field.

• YouTube
• 36 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Great Ideas in Theoretical Computer Science: Countability and Diagonalization

Explore fundamental concepts in theoretical computer science, including countability, diagonalization, and set theory, with a focus on infinite sets and cardinality.

• YouTube
• 1 hour 14 minutes
• On-Demand
• Free Video

Association for Computing Machinery (ACM)

A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization

Explore adaptive complexity in submodular maximization, covering nonmonotone approximation and hardness. Gain insights into this advanced computational topic through a concise presentation of key concepts and findings.

• YouTube
• 24 minutes
• On-Demand
• Free Video