Simons Institute Courses

Associative Memories as a Building Block in Transformers

Explore associative memories in Transformers, their role in storing knowledge, and how gradients and over-parameterization affect their learning and capacity.

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

Dynamic PageRank: Additive Error and Batch Recomputation

Explores dynamic PageRank algorithms, proving hardness of relative error approximations and demonstrating efficiency of batch recomputation for L1 error metric in dynamic graph settings.

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

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates

Explore dynamic algorithms for packing-covering LPs using multiplicative weight updates, focusing on near-optimal approximation algorithms and complexity analysis in dynamic settings.

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

Online List Labeling - Breaking the Log^2 N Barrier

Explores a randomized data structure for online list labeling, improving the upper bound to O(log^{3/2} n) items moved per insertion/deletion, breaking the long-standing log^2 n barrier.

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

Practical Dynamic Graph Algorithms - Data Structures and Connections Between Models

Explore efficient data structures and techniques for dynamic graph algorithms across multiple computational models, focusing on k-core decomposition, densest subgraph, and triangle counting problems.

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

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

Recent Progress on Submodular Function Minimization

Explore recent advancements in submodular function minimization algorithms, leveraging convex optimization methods to address open questions and improve efficiency in discrete optimization.

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

Quotient Sparsification for Submodular Functions

Explores sparsification of matroids and submodular functions, unifying graph and hypergraph cut sparsifiers with applications to set systems and algorithmic efficiency.

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