Computational Complexity Courses and Certifications

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

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

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

BIMSA

When and Why Do Efficient Algorithms Exist for Constraint Satisfaction and Beyond

Explore the mathematical structures behind efficient algorithms for constraint satisfaction problems and beyond, focusing on polymorphisms and their role in computational complexity.

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

Centre de recherches mathématiques - CRM

Tensor Reconstruction Beyond Constant Rank

Explorez les algorithmes efficaces pour calculer le rang tensoriel et reconstruire des circuits algébriques restreints, améliorant les résultats existants pour les tenseurs de rang faible mais non constant.

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

Simons Institute

Promise Algebra: A Functional Approach to Non-Deterministic Computations

Algebraic approach to modeling non-determinism in computational processes, using promise algebra and history-dependent choice functions to analyze complexity and generate strategies.

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

Simons Institute

Applications of Sub-linear Algorithms in Other Fields

Explore how sub-linear algorithms impact diverse fields, enhancing efficiency and scalability in data analysis and problem-solving across disciplines.

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

Kolmogorov-Seminar

Basic Results About Learning in Computational Complexity - March 2023

Dive into fundamental concepts of computational complexity and learning theory through Bruno Bauwens' detailed exploration at the prestigious Kolmogorov seminar.

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

Centre International de Rencontres Mathématiques

Randomness and Complexity - Lecture 2

Explore connections between randomness and complexity in mathematics, focusing on advanced concepts and their applications in discrete mathematics and computer science.

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

Centre International de Rencontres Mathématiques

A Quick and Partial Survey on the Complexity of Query Answering

Explore the complexity of query answering in this survey, covering key concepts and recent developments in discrete mathematics and logic.

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

Centre International de Rencontres Mathématiques

Et si SAT était vraiment difficile? Quelques conséquences des hypothèses ETH - Lecture

Explorez les implications des hypothèses ETH sur la difficulté du problème SAT et ses conséquences en informatique théorique et complexité algorithmique.

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

Kolmogorov-Seminar

Cutting Figures into Equal Parts Using Grid Lines and SAT Solvers - May 27, 2024

Explore computational techniques for solving geometric cutting problems using SAT solvers, with practical applications in grid-based figure partitioning and combinatorial optimization.

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

Kolmogorov-Seminar

Полудуплексная Коммуникационная Сложность: Разные Виды Adversary

Dive into the intricacies of half-duplex communication complexity, exploring different adversary types and their impact on complexity measures through concrete examples and theoretical analysis.

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

Kolmogorov-Seminar

Lempel-Ziv Algorithm: Complexity Analysis and Automaton Conversion

Delve into the Lempel-Ziv algorithm's complexity analysis, exploring its relationship with superadditive functions and automaton conversion principles in computational theory.

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