Algorithm Analysis Courses and Certifications

Paul G. Allen School

Money, Circuits, Mythic Figures, and More - Theory in the Allen School

Diverse theoretical computer science research: algorithms, data structures, complexity, combinatorics, and economics. Insights from UW Allen School's theory group on cutting-edge topics.

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

Ryan O'Donnell

Great Ideas in Theoretical Computer Science - Approximation Algorithms

Explore approximation algorithms for NP-hard problems, focusing on Vertex Cover, k-Coverage, and Traveling Salesperson. Learn techniques to find near-optimal solutions efficiently.

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

Ryan O'Donnell

Undergrad Complexity at CMU - Oracle Turing Machines and P^NP

Explore oracle Turing machines and P^NP in computational complexity theory, focusing on solving algorithms, consequences, and the Minimum Circuit Problem.

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

Association for Computing Machinery (ACM)

STOC 2020 - Online Algorithms

Explore online algorithms, including caching with time windows, vector balancing, and primal-dual matching. Learn about recent advancements and open problems in this dynamic field of computer science.

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

Ryan O'Donnell

Fast Fourier Transform - Lecture 7c of CS Theory Toolkit

Explore the Fast Fourier Transform algorithm and its application in efficient integer multiplication, with insights from a CMU graduate-level computer science theory course.

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

Ryan O'Donnell

Time-Space Tradeoffs for SAT - Graduate Complexity Lecture at CMU

Explore time/space tradeoffs for SAT in this graduate-level complexity theory lecture, covering key results, proofs, and techniques like padding and alternation elimination.

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

Ryan O'Donnell

Great Ideas in Theoretical Computer Science: Time Complexity - Spring 2016

Explore time complexity in theoretical computer science, covering running time, worst-case scenarios, and common runtime scaling, with practical examples and formal definitions.

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

Ryan O'Donnell

Time Complexity

Learn about time complexity in algorithms, covering input sizes, running time analysis, worst-case scenarios, and efficiency considerations for various computational problems.

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

Ryan O'Donnell

Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit

Explore derandomization techniques using expander graphs to reduce error in randomized algorithms without significantly increasing random bits used.

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

Alan Turing Institute

Optimisation - An Introduction: Professor Coralia Cartis, University of Oxford

Explore optimization techniques, from basic concepts to advanced methods, covering minimizers, derivatives, quadratic functions, and gradient methods for solving complex mathematical problems.

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

Institute for Advanced Study

An Introduction to Boolean Function Analysis - Dor Minzer

Explore Boolean function analysis, covering influences, PCP theory, and hypercontractive inequalities. Gain insights into fundamental concepts and advanced techniques in discrete mathematics and theoretical computer science.

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

Association for Computing Machinery (ACM)

Breaching the 2-Approximation Barrier for Connectivity Augmentation

Explore advanced techniques in network design, focusing on connectivity augmentation and its reduction to the Steiner Tree problem. Learn about novel approximation algorithms and open challenges in the field.

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

Association for Computing Machinery (ACM)

Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

Explore unexpected findings on Kolmogorov complexity, including hardness results, limits, conjectures, and implications for pseudorandom generators and computational complexity.

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

Association for Computing Machinery (ACM)

An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games

Explore advanced cutting plane methods for convex optimization and games, covering improved algorithms, runtime bottlenecks, data structures, and practical applications in computational mathematics.

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

Association for Computing Machinery (ACM)

A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization

Explore adaptive complexity in submodular maximization, covering nonmonotone approximation and hardness. Gain insights into this advanced computational topic through a concise presentation of key concepts and findings.

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