Complexity Theory Courses and Certifications

Alan Turing Institute

Alan Turing and the Other Theory of Computing and Can a Machine Be Conscious?

Explore Turing's lesser-known 1948 paper on numerical computation and its impact on complexity theory. Discover how it unifies two major traditions in computational theory.

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

Society for Industrial and Applied Mathematics

Optimization, Complexity and Math - Can We Prove P!=NP by Gradient Descent?

Explore optimization, complexity, and mathematics with Avi Wigderson. Delve into perfect matchings, symbolic matrices, and operator scaling, connecting diverse areas of mathematics and computer science.

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

Simons Institute

The Long Path to Square Root of d Monotonicity Testers

Explore directed isoperimetry and its application to monotonicity testing, analyzing directed random walks on product domains for optimal testers in Boolean functions on hypergrids.

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

Centre International de Rencontres Mathématiques

Randomness and Complexity - Lecture 1

Explore the intersection of randomness and complexity in mathematics, delving into key concepts and their applications in discrete mathematics and computer science.

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

Centre International de Rencontres Mathématiques

Complexity and the Hat

Explore complexity through mathematical concepts, focusing on unique perspectives and innovative approaches in discrete mathematics and computer science.

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

Centre International de Rencontres Mathématiques

Pseudodeterministic Constructions and rK^t - Tutorial 3

Explore pseudodeterministic constructions and rK^t in this advanced mathematics tutorial by Igor Carboni Oliveira, delving into randomness, information, and complexity theory.

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

ACM SIGPLAN

The Complex(ity) Landscape of Checking Infinite Descent

Explore the complexity of checking Infinite Descent in cyclic proof systems, examining various criteria and their parameterized time complexities to improve automatic verification techniques.

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

Centre de recherches mathématiques - CRM

Finding Barriers for Lower Bounds on Tensor Rank

Explore challenges in proving lower bounds on tensor rank, including barriers to "rank methods" and potential improvements using varieties with specific properties.

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

ACM SIGPLAN

Positive Almost-Sure Termination: Complexity and Proof Rules

Explore complexity and proof rules for Positive Almost-Sure Termination in probabilistic programming, including recursion-theoretic analysis and novel proof techniques using transfinite ordinals.

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

CLEA, Free University of Brussels (VUB)

Edgar Morin's The Method: Introduction to Complex Thinking and Critical Analysis

Delve into Edgar Morin's complex philosophical masterwork 'The Method' through an expert analysis of key concepts like dialogic thinking, recursive loops, and constructivist perspectives on reality and perception.

• YouTube
• 1 hour 40 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

Introduction to the Theory of Computing - Stanford

Explore fundamental concepts of theoretical computer science, including automata, computability, and complexity theory, with practical applications and algorithmic fairness.

• YouTube
• 20 hours
• On-Demand
• Free Video

Advanced Data Structures in Java

1237 ratings at Coursera

Explore advanced data structures and algorithms for real-world problem-solving, focusing on graphs and their applications in route planning, network optimization, and resource allocation.

• Coursera
• 1 day 4 hours 42 minutes
• On-Demand
• Free Online Course (Audit)

Design and Analysis of Algorithms

1 review

Comprehensive exploration of advanced algorithm design and analysis, covering diverse topics from interval scheduling to cryptography and distributed systems.

• MIT OpenCourseWare
• 39 hours
• On-Demand
• Free Video

Complexity Theory - Running Time Analysis of Algorithms

2355 ratings at Udemy

Learn Asymptotic Complexity, Running Times Analysis (O, Ω, θ) and Complexity Classes (P and NP)

• Udemy
• 1 hour 56 minutes
• On-Demand
• Free Online Course