Simons Institute Courses

Decremental Shortest Paths Against an Adaptive Adversary

Explore efficient algorithms for maintaining shortest paths in dynamic graphs undergoing deletions, with a focus on near-optimal deterministic data structures and adaptive adversary scenarios.

• YouTube
• 1 hour 2 minutes
• Self-Paced
• Free Video

Dynamic Graph Algorithms - What We Know and What We Don't - Richard M. Karp Distinguished Lecture

Explore dynamic graph algorithms, their applications, and recent breakthroughs. Learn about current research, techniques, and open questions in this critical field of computer science.

• YouTube
• 1 hour 12 minutes
• Self-Paced
• Free Video

Parallelism in Dynamic Graph Algorithms

Explore parallelism in dynamic data structures through batch algorithms and graph streaming, enabling efficient handling of concurrent updates and queries in graph algorithms.

• YouTube
• 1 hour
• Self-Paced
• Free Video

Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy

Explore techniques for optimizing dynamic-graph data structures on multicores, focusing on locality-first strategies to enhance performance for large-scale problems in real-world applications.

• YouTube
• 48 minutes
• Self-Paced
• Free Video

Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models

Explore recent advancements in diversity maximization for data summarization and recommendation systems, focusing on offline and composable coreset models for handling massive datasets efficiently.

• YouTube
• 46 minutes
• Self-Paced
• Free Video

Approximating Edit Distance in the Fully Dynamic Model

Explore recent advancements in dynamic algorithms for approximating edit distance, covering state-of-the-art results and open questions in this fundamental computer science problem.

• YouTube
• 50 minutes
• Self-Paced
• Free Video

Faster High Accuracy Multi-Commodity Flows via Graph Techniques

Explore graph techniques to accelerate multi-commodity flow algorithms, improving accuracy and efficiency. Discover connections to linear programming and open problems in algorithm design.

• YouTube
• 45 minutes
• Self-Paced
• Free Video

Minimum Isolating Cuts - A New Tool for Solving Minimum Cut Problems

Explore a powerful new tool for solving minimum cut problems in combinatorial optimization, with applications to global, Steiner, and all-pairs min-cut algorithms.

• YouTube
• 41 minutes
• Self-Paced
• Free Video

On Dynamic Graph Approximations - The Case of J-Trees

Explores dynamic maintenance of j-trees in graph theory, discussing implications for cut-based optimization, maximum flows, and minimum cost-flow computations in algorithmic design.

• YouTube
• 53 minutes
• Self-Paced
• Free Video

On Engineering Dynamic Graph Algorithms

Explore challenges, techniques, and best practices for engineering dynamic graph algorithms, with insights on experimental approaches and design considerations.

• YouTube
• 52 minutes
• Self-Paced
• Free Video

Dynamic Graphs on the GPU

Explore GPU-accelerated techniques for dynamic graph algorithms, focusing on efficient data structures and parallel processing for real-time graph updates and analysis.

• YouTube
• 58 minutes
• Self-Paced
• Free Video

Accelerating the Multiplicative-Weights Framework for Graph Linear Programs

Accelerated multiplicative-weight updates framework for solving packing/covering LPs in graph optimization, reducing iterations from Θ(m) to ~Θ(√m) using a packing version of Min-IP oracle.

• YouTube
• 53 minutes
• Self-Paced
• Free Video

Recent Progress on Sublinear Time Algorithms for Maximum Matching - Lower Bounds

Explore recent techniques for estimating maximum matching size, focusing on lower bounds and correlation decay methods that lead to super-linear lower bounds for approximations above 2/3.

• YouTube
• 47 minutes
• Self-Paced
• Free Video

P-Smallness of Increasing Families

Explore increasing families in finite sets, thresholds, and p-smallness. Learn about p-biased product measures and their applications in random discrete structures.

• YouTube
• 58 minutes
• Self-Paced
• Free Video

Nearly All K-SAT Functions Are Unate

Explore the prevalence of unate functions in k-SAT, resolving a 2003 conjecture and unveiling structural insights into Boolean satisfiability problems.

• YouTube
• 1 hour 5 minutes
• Self-Paced
• Free Video