Complexity Theory Courses and Certifications

Ryan O'Donnell

Undergrad Complexity at CMU - From P-Completeness to PSPACE-Completeness

Explore P-completeness, reductions, and PSPACE-completeness in computational complexity theory, covering key concepts like the Cook-Levin Theorem and TQBF.

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

Ryan O'Donnell

Undergrad Complexity at CMU - Savitch's Theorem and NL

Explore Savitch's Theorem and NL in computational complexity theory, focusing on space complexity, recursion, and pseudocode implementation for advanced undergraduate-level understanding.

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

Ryan O'Donnell

Undergrad Complexity at CMU - NP

Explore NP complexity, verification, and key features in computational theory. Delve into stronger conjectures, brute force algorithms, and proofs for squares and colors.

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

Ryan O'Donnell

Undergrad Complexity at CMU - SAT

Explore the intricacies of SAT in computational complexity theory, covering Boolean circuits, algorithms, and CNF formulas in this comprehensive undergraduate lecture.

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

Ryan O'Donnell

Undergrad Complexity at CMU - Problems in P

Explore computational complexity theory, focusing on problems in P, simulations, and Turing machine variants. Learn about time hierarchy, natural problems, and efficient algorithms.

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

AGU

Dragon-Kings, Black-Swans and Prediction - Lorenz Lecture

Explore extreme events, their predictability, and impact on complex systems through statistical physics and nonlinear dynamics in this insightful lecture by D. Sornette.

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

Complexity Explorer

Computing the Uncomputable: The Coding Theorem Method - Unit 6, Module 2

Explore the Coding Theorem Method for computing uncomputable functions, delving into algorithmic information dynamics and its applications in causality and living systems.

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

Institute for Advanced Study

Discussion on MIP* = RE

Explore the groundbreaking MIP* = RE theorem with MIT's Anand Natarajan, delving into its implications for quantum computing, complexity theory, and the foundations of mathematics.

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

Harvard CMSA

The P vs. NP Problem - An Existential Question for Mathematics

Explore the profound P vs NP problem and its implications for mathematics, computing, and automated proof search in this millennium prize lecture by Harvard's Madhu Sudan.

• YouTube
• 1 hour
• Self-Paced
• Free Video

Paul G. Allen School

Computational Complexity and Explanations in Physics

Explore how computational intractability shapes physical explanations, from quantum mechanics interpretations to black hole paradoxes and thermodynamics.

• YouTube
• 1 hour 11 minutes
• Self-Paced
• Free Video

GKR Protocol and IP=PSPACE - Lecture 3

Delve into advanced cryptography concepts focusing on IP=PSPACE applications and the GKR Protocol through detailed mathematical proofs and theoretical frameworks.

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

Probabilistically Checkable Proofs via GKR and Interactive Arguments - Lecture 4

Delve into probabilistically checkable proofs (PCP), exploring their construction through GKR protocol and interactive succinct arguments for NP in advanced cryptography.

• YouTube
• 1 hour 30 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds

Explore advanced connections between circuit analysis algorithms and nonuniform lower bounds, revealing new win-win results that could refute the Orthogonal Vectors Conjecture.

• YouTube
• 2 hours 4 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

The P vs. NP Problem

Explore the famous P vs. NP problem, its evolution over 50 years, and the diverse research directions it has spawned in computational complexity theory.

• YouTube
• 1 hour 14 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Upper and Lower Bounds for the Linear Ordering Principle

Explore advanced complexity theory through upper and lower bounds for the Linear Ordering Principle, examining its position between promise complexity classes and resolving key open questions.

• YouTube
• 1 hour 11 minutes
• Self-Paced
• Free Video