Simons Institute Courses

Stochastic Minimum Vertex Cover with Few Queries: A 3/2-Approximation

Explore a 3/2-approximation algorithm for stochastic vertex cover using O(n/p) non-adaptive queries, improving upon previous 2-approximation methods and discussing extensions to correlated edge realizations.

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

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs

Explore advanced algorithms for dynamic maximum matching using Ordered Ruzsa-Szemeredi Graphs, improving update time to n^{o(1)} * ORS(n) and reducing the problem to a combinatorial bound.

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

New Algorithms for Directed Spanner Problems and Generalizations

Explore recent advancements in directed spanner algorithms, including online and offline settings, weighted variants, and buy-at-bulk extensions.

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

Fast Streaming Euclidean Clustering with Constant Space

Explore streaming algorithms for k-median and k-means clustering, achieving constant space complexity independent of data size and aspect ratio. Improve space and update time for approximate subspace embeddings.

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

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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• 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
• On-Demand
• Free Video

Challenges in Research on Practical Algorithms

Explore challenges in developing practical algorithms, focusing on real-world applications and industry perspectives in computer science research.

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

Well-being, AI, and You - Developing AI-based Technology to Enhance our Well-being

Explore AI's potential to enhance personal well-being through innovative technologies, focusing on practical applications and future developments in this emerging field.

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

Semiring Semantics

Explore semiring semantics in logic, evaluating statements with values beyond true/false. Learn applications in database queries, provenance analysis, and extensions to various logical systems.

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