Computational Complexity Courses and Certifications

Simons Institute

Circuit Lower Bounds from Algorithm Design - An Overview I

Explore circuit lower bounds in computational complexity, focusing on algorithm design techniques and their implications for NP problems and Boolean functions.

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

Simons Institute

Lower Bounds on the Size of Linear Programs

Explore computational complexity, linear programming, and extended formulations in this lecture on lower bounds for linear program sizes, featuring geometric views and advanced topics.

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

Simons Institute

Computational Barriers in Statistical Estimation and Learning

Explore statistical estimation challenges, information theory, and computational barriers in high-dimensional settings with Stanford's Andrea Montanari in this Richard M. Karp Distinguished Lecture.

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

IEEE

Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

Explore the complexity theory concept of non-deterministic quasi-polynomial time and its average-case hardness for ACC circuits in this advanced computer science presentation.

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

IEEE

Waring Rank, Parameterized and Exact Algorithms

Explore Waring rank and its applications in parameterized and exact algorithms, gaining insights into computational complexity and problem-solving techniques.

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

Complexity Explorer

Computing the Uncomputable: The Coding Theorem Method - Unit 6, Module 2

Explore the Coding Theorem Method for computing uncomputable functions, delving into algorithmic information dynamics and its applications in causality and living systems.

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

Simons Institute

Explicit SoS Lower Bounds from Small-Set High Dimensional Expanders

Explores explicit CSPs hard for Sum-of-Squares hierarchy using small-set high dimensional expanders, introducing new isoperimetric inequality for Square Cayley Complexes to construct optimally hard XOR-families.

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

Churchill CompSci Talks

Sublinear Time Property Testers - Algorithms for Efficient Function Analysis

Explore sublinear time property testers for efficient algorithm design. Learn about relaxed decision problems, fast testers, and applications in graph theory and string processing.

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

Association for Computing Machinery (ACM)

Automating Cutting Planes is NP-Hard

Explore the complexity of automating cutting planes in computational geometry, covering historical context, algorithmic challenges, and proof systems.

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

Association for Computing Machinery (ACM)

The Communication Complexity of Truthful vs Non-Truthful Combinatorial Auctions

Explore communication complexity in combinatorial auctions, comparing truthful and non-truthful mechanisms through theoretical analysis and proof techniques.

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

Association for Computing Machinery (ACM)

Sharp Threshold Results for Computational Complexity

Explore cutting-edge research on computational complexity, focusing on sharp threshold results, hardness magnification, and probabilistic formulas in this advanced theoretical computer science talk.

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

Simons Institute

Hidden Symmetries of Computational Problems

Explore hidden symmetries in computational problems, uncovering geometric methods for optimization and sampling with insights from experts in mathematics and quantum computing.

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

Simons Institute

Optimal Iterative Algorithms for Problems With Random Data

Explore advanced iterative algorithms for solving problems with random data, focusing on computational complexity in statistical inference.

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

Simons Institute

Parameterized Inapproximability of the Minimum Distance Problem over All Fields

Explores inapproximability of Minimum Distance Problem for linear codes over finite fields, proving W[1]-hardness. Extends results to Shortest Vector Problem on integer lattices.

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