Complexity Theory Courses and Certifications

Dr Trefor Bazett

Kolmogorov Complexity and Random Numbers - Understanding Pi Through Computational Theory

Explore Kolmogorov Complexity and its connection to randomness through an engaging mathematical journey that proves the infinity of prime numbers using computational concepts.

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

Ryan O'Donnell

Graduate Complexity Theory

Dive into advanced computational complexity theory with graduate-level lectures covering hierarchy theorems, circuits, interactive proofs, and cutting-edge research topics.

• YouTube
• 1 day 11 hours 50 minutes
• On-Demand
• Free Video

Centre de recherches mathématiques - CRM

Multiplayer Parallel Repetition for Three-Player Games on Binary Inputs

Explorez la répétition parallèle dans les jeux multijoueurs, en mettant l'accent sur les jeux à trois joueurs avec entrées binaires. Découvrez les dernières avancées et techniques d'analyse.

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

International Centre for Theoretical Sciences

Computational Complexity in Theory and in Practice by Richard M. Karp

Explore the contrast between theoretical and practical approaches to algorithm efficiency, covering complexity classes, NP-completeness, approximation algorithms, and real-world applications.

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

Institute for Advanced Study

Towards a Complexity Theory for Fully Quantum Problems

Explore quantum complexity theory and its applications in solving fully quantum problems, focusing on cutting-edge research and potential breakthroughs in quantum computing.

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

Hausdorff Center for Mathematics

Dimension, Complexity and K Theory

Explore connections between dimension theory, complexity, and K-theory in mathematics, focusing on applications in topology and geometry. Gain insights into cutting-edge research in these interconnected fields.

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

International Centre for Theoretical Sciences

Introduction to Geometric Complexity Theory by Christian Ikenmeyer

Explore geometric complexity theory, a cutting-edge approach to solving fundamental problems in computational complexity and algebraic geometry.

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

Simons Institute

Fine-Grained Complexity 3 - Logic and Algorithms in Database Theory and AI

Explore advanced concepts in fine-grained complexity theory, focusing on algorithmic challenges and their implications for database theory and AI.

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

IEEE

Complexity Theory - Session 1A

Explore complexity theory in this IEEE conference session, delving into advanced concepts and recent developments in computational complexity.

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

IEEE

NEXP is Contained in MIP* - Complexity Theory Breakthrough

Explore groundbreaking results in computational complexity theory, examining the relationship between NEXP and MIP* with insights from experts Anand Natarajan and John Wright.

• YouTube
• 22 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

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

Simons Institute

Prediction, Generalization, and Complexity: Classical Statistical Theory Revisited - Part 1

Explore classical statistical decision theory's insights on prediction error, generalization gap, and model complexity. Examine fixed-X perspective limitations and extend concepts to random-X settings in machine learning.

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

Simons Institute

Prediction, Generalization, and Complexity in Statistical Decision Theory - Part 2

Explore statistical decision theory's insights on prediction error, generalization gap, and model complexity. Examine fixed-X vs. random-X perspectives and their implications for machine learning.

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

Centre International de Rencontres Mathématiques

Complexity Theory Through the Lens of Kolmogorov Complexity - Tutorial 2

Explore complexity theory through Kolmogorov complexity in this mathematical tutorial by Igor Carboni Oliveira, recorded at CIRM's thematic meeting on randomness, information, and complexity.

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