Simons Institute Courses

Sublinear Algorithms for Correlation Clustering

Explore sublinear algorithms for correlation clustering, focusing on a 3+eps approximation method using LCA probes, MPC rounds, and dynamic updates. Analyze technical results for maximal independent set computation.

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

Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs - Towards Constructive Matching Sparsifiers

Explore approaches for designing fast dynamic algorithms for approximate matchings, focusing on fully dynamic settings and the concept of matching sparsifiers in graph theory.

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

Maximum Matching in O(log log n) Passes in Dynamic Streams

Explore an algorithm for approximating maximum matching in dynamic streams, achieving O(1)-approximation in O(log log n) passes and O(n poly log n) space, with lower bound proof.

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

Almost-Optimal Sublinear Additive Spanners in Graph Theory

Explore sublinear additive spanners in graph theory, focusing on optimal stretch functions and size bounds for undirected unweighted graphs. Learn about recent advancements and their implications.

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

Planar Partition Oracles for Bounded Degree Graphs in Polynomial Time

Explore planar graph partition oracles for bounded degree graphs, focusing on hyperfinite decompositions and their applications in sublinear algorithms and property testing.

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

Sparsification: Graphs, CSPs and Codes - Sublinear Graph Simplification

Explore graph sparsification, CSP compression, and code sparsification techniques. Learn about cutting-edge research in sublinear graph simplification and its applications to various domains.

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

Robust Optimization and Generalization

Explore robust optimization's history and its modern machine learning applications, focusing on performance certification and practical challenges in ML systems.

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

Conditional Sampling for Distribution Testing

Explore conditional sampling techniques for distribution testing, focusing on efficient algorithms and their applications in statistical analysis.

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

Games of Imperfect Information - Designing Signaling Strategies

Explore strategies for designing signaling in games with asymmetric information, focusing on principal-agent interactions and their applications in real-world scenarios.

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

Symbolic Finite- and Infinite-state Synthesis

Explore innovative abstraction-refinement techniques for LTL synthesis, enhancing scalability and addressing infinite-state challenges through liveness refinements and symbolic representations.

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

Attractor Decompositions in Games and Automata

Explore attractor decompositions in graphs, their role in parity games, and applications to automata theory. Learn about structural complexity measures and strategy analysis.

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

Descriptive Complexity for Distributed Computing and Neural Networks

Explore logics capturing distributed computing and neural network models, including graph neural networks. Dive into game-theoretic semantics and computational logic connections.

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

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
• Self-Paced
• Free Video

Localized Attractor Computations for Infinite-State Games

Explore symbolic methods for solving infinite-state games, focusing on localized attractor computations in sub-games to enhance efficiency and tackle complex problem instances.

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

Computing a Fixed Point of Contraction Maps in Polynomial Queries

Efficient algorithm for computing fixed points of contraction maps, with potential implications for solving simple stochastic games and related computational problems.

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