Computational Complexity Courses and Certifications

Institute for Advanced Study

Simulating Time With Square-Root Space

Delve into a groundbreaking simulation technique that improves on a 50-year-old algorithm, showing how multitape Turing machines running in time t can be simulated in O(t√log t) space.

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

Simons Institute

Can We Get Asymptotic Safety Guarantees Based On Scalable Oversight?

Explore the theoretical foundations of scalable oversight for AI safety, focusing on a new "prover-predictor game" variant of debate that addresses obfuscated arguments while requiring less computational complexity than previous methods.

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

Institute for Advanced Study

How Efficiently Can We Solve Unique Games? - Lecture

Explore the computational complexity of Unique Games and their efficient solutions in this insightful talk by Yotam Dikstein.

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

Centre for Networked Intelligence, IISc

Applications of Algebraic Complexity to Unsupervised Learning

Delve into advanced algebraic complexity theory and its applications in unsupervised learning algorithms, exploring computational hardness of multivariate polynomials and efficient learning techniques.

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

Kolmogorov-Seminar

One-Way Computable Transformations - The Barmalias-Zhang Example

Dive into the mathematical exploration of one-way computable transformations through the Barmalias-Zhang example, examining its significance in computational complexity theory.

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

Kolmogorov-Seminar

Rectangles, Complexity and Games in Communication Theory - December 4, 2023

Delve into communication complexity theory through rectangles, exploring inequality principles, combinatorial strategies, and their applications in computational game theory.

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

Institute for Advanced Study

Dot-Product Proofs for Circuit Satisfiability and Cryptographic Systems

Delve into probabilistic proof systems and dot-product proofs, exploring their applications in circuit satisfiability, MAX-LIN approximation, and cryptographic verification complexity.

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

Institute for Advanced Study

Lower Bound Barriers in Complexity Theory and Overcoming Them With Geometry

Explore the evolution of complexity theory's lower bound barriers through geometric perspectives, from linear algebra to advanced mathematical concepts in algebraic geometry and representation theory.

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

QuICS

Conditional Lower Bounds for Algorithms with Pre-processed Advice

Explore the tradeoffs between resources in algorithmic tasks with pre-processing phases, examining conditional lower bounds based on problems like 3SUM Indexing and potential quantum extensions.

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

Centre International de Rencontres Mathématiques

Effective Bounds for Polynomial Systems Defined Over the Rationals - Lecture 1

Delve into effective bounds for polynomial systems with rational coefficients, exploring arithmetic Bézout inequality, zero-dimensional systems, Nullstellensatz, and Perron's theorem for implicitization.

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

Kolmogorov-Seminar

Binary Addition Algorithm Through Window Observation - 2025-04-07

Explore how binary addition algorithms emerge from analyzing bit triples through adjacent windows, leading to a simplified zig-zag approach for computation.

• YouTube
• 2 hours 15 minutes
• On-Demand
• Free Video

Institute for Advanced Study

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem

Delve into the sample complexity of smooth boosting algorithms and their connection to Impagliazzo's hardcore theorem, exploring optimal parameters and necessary size loss in circuit complexity.

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

Kolmogorov-Seminar

Bishop's Up Crossing Inequality Revisited

Explore Bishop's constructive approach to sequence convergence through crossing inequalities, following Andreev's proof methods for bounded sequences in computational complexity theory.

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

Kolmogorov-Seminar

Upcrossing Inequalities, Ergodic Theorem and Barmpalias-Lewis-Pye - Part 2

Explore advanced mathematical connections between crossing inequalities, Birkhoff ergodic theorem, and Barmpalias-Lewis-Pye results on Martin-Löf random reals.

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

Kolmogorov-Seminar

Learning Sets - Introductory Talk

Explore how classical computability-based learning concepts apply to set learning in this foundational seminar on computational complexity theory.

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