Simons Institute Courses

A Quasi-Monte Carlo Algorithm for Smooth Kernel Evaluation

Explore a novel data structure for density queries, combining discrepancy theory and LSH to build sparse coresets and enhance smooth kernel evaluation algorithms.

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

Recent Progress on Euclidean Spanners

Explore recent advancements in Euclidean spanners, including sparse, light, fault-tolerant, and dynamic variants, while discovering outstanding open problems in the field.

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

Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier

Explore efficient algorithms for agnostic, proper learning of monotone Boolean functions, overcoming previous limitations and achieving near-optimal runtime complexity.

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

Linear Sketching Hypergraph Sparsifiers

Explore linear sketching techniques for hypergraph sparsification, examining upper and lower bounds, dynamic streaming algorithms, and novel methods like random fingerprinting for efficient cut preservation.

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

Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Explore cut sparsification of hypergraphs, focusing on submodular functions. Learn about new bounds, polynomial bounds, and succinct representation techniques for various submodular function families.

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

The Approximate Structure of Triangle-Free Graphs

Explore the structure of dense triangle-free graphs and learn about efficient algorithms for computing their approximate representations using smaller graphs.

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

Sparsification for Communication-Efficient Distributed Symmetry-Breaking

Explore sparsification techniques for efficient distributed algorithms, focusing on local symmetry-breaking problems in graph theory and the CONGEST model.

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

Maximal Matching in Bounded-deletion Streams

Explore maximal matching in bounded-deletion graph streams, analyzing space complexity as a function of deletion parameter K. Gain insights into algorithmic techniques and lower bound results.

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

Graphs with Large Edge Weights for Shortest Path Structure - Sublinear Graph Simplification

Explore the relationship between graph shortest paths and edge weight ratios, examining reweighting techniques to preserve path structures.

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

Sparsifying Set Systems for Coverage Problems

Explore recent advancements in sparsifying set systems for coverage problems, focusing on sublinear graph simplification techniques.

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

Improved Streaming Algorithms for Max-DICUT via Local Snapshots

Explore advanced streaming algorithms for Max-DICUT problem, focusing on local graph snapshots to surpass the 4/9 approximation in sublinear space.

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

Approximating Maximum Matching Requires Almost Quadratic Time

Explore algorithms for estimating maximum matching size, focusing on recent advancements and lower bounds. Gain insights into subquadratic time complexity and its limitations in graph theory.

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

Online Algorithms for Spectral Hypergraph Sparsification

Explore online algorithms for spectral hypergraph sparsification, focusing on space-efficient methods for handling streaming hyperedges and producing accurate sparsifiers.

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

On (1 + ε)-Approximate (Vertex) Cut Sparsifiers

Explore advanced graph compression techniques for planar and quasi-bipartite graphs, focusing on high-quality cut sparsifiers and their size bounds. Analyze contraction-based approaches and their limitations.

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

Small Space Differentially Private Graph Algorithms in the Continual Release Model

Explore sublinear space differentially private graph algorithms for continual release, covering densest subgraphs, k-core decomposition, maximum matching, and vertex cover.

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