Complexity Courses and Certifications

Ryan O'Donnell

Undergrad Complexity at CMU - Randomized Complexity- RP, coRP, and ZPP

Explore randomized complexity classes RP, coRP, and ZPP, covering probabilistic Turing machines, error amplification, and nondeterminism in computational complexity theory.

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

Ryan O'Donnell

Undergrad Complexity at CMU - The Immerman-Szelepcsényi Theorem

Explore the Immerman--Szelepcsényi Theorem in computational complexity theory, covering key concepts, proofs, and implications for nondeterministic space complexity classes.

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

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

Ryan O'Donnell

Undergrad Complexity at CMU - Turing Machines

Explore Turing Machines in computational complexity theory, covering formalization, the Turing Thesis, examples, and mathematical definitions for a comprehensive understanding.

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

Institute for Advanced Study

Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers - Toniann Pitassi

Explore lower bounds in complexity theory, communication complexity, and sunflowers. Delve into Boolean circuits, formulas, and key lemmas with expert insights from Toniann Pitassi.

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

Institute for Advanced Study

Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory - Robert Robere

Explore advanced concepts in complexity theory, including proofs, circuits, and communication, with a focus on lower bounds and their implications for computational limits.

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

Institute for Advanced Study

Proof and Circuit Complexity - Robert Robere

Explore proof and circuit complexity with Robert Robere, delving into Boolean circuits, monotone circuits, slice functions, and the Click function to understand computational limitations.

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

Institute for Advanced Study

A Brief Tour of Proof Complexity - Lower Bounds and Open Problems - Toniann Pitassi

Explore proof complexity, lower bounds, and open problems in computer science and discrete mathematics with insights on proof systems and their limitations.

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

GOTO Conferences

Runaway Complexity in Big Data Systems and a Plan to Stop It

Explore strategies to combat complexity in big data systems, focusing on immutability, the Lambda Architecture, and a combination of batch and real-time processing for more efficient data management.

• YouTube
• 45 minutes
• On-Demand
• Conference Talk

Devoxx

Removing Complexity from Integration Tests Using Testcontainers

Simplify integration testing for microservices using Testcontainers. Learn to create isolated, Docker-based environments for databases and services, enhancing test reliability and ease of implementation.

• YouTube
• 43 minutes
• On-Demand
• Conference Talk

Rawkode Academy

Introduction to Kapitan - Managing Complexity in Kubernetes and Terraform Deployments

Explore Kapitan, a powerful tool for managing complex deployments in Kubernetes and Terraform. Learn its key features, vocabulary, and practical applications for efficient configuration management.

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