Simons Institute Courses

Hypercontractivity Inequality on Epsilon-Product Spaces

Explores hypercontractivity inequality on ε-product spaces, generalizing previous results and capturing new spaces like spectral high-dimensional expanders. Applications include small-set expansion theorems.

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

Reverse Hypercontractivity and Improved Sampling in High Dimensional Expanders

Explore reverse hypercontractivity in high-dimensional expanders, its connection to mixing and sampling, and discover new Chernoff-like bounds in these mathematical structures.

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

Explicit Orthogonal and Unitary Designs

Explore advanced mathematical constructions for orthogonal and unitary groups, focusing on explicit designs with optimal cardinality and seed length for complex matrix applications.

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

Query Optimization and Evaluation - Instance Optimality

Explore instance optimality in query optimization and evaluation, focusing on advanced techniques for enhancing database performance and efficiency.

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

Query Optimization and Evaluation 3 - Variable Elimination and Tensor Decomposition

Explore variable elimination and tensor decomposition techniques for optimizing and evaluating complex queries in database systems and AI applications.

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

Query Optimization and Evaluation 2 - Worst-Case Optimal Join Algorithms

Explore worst-case optimal join algorithms for efficient query processing, focusing on advanced techniques to enhance database performance and optimize complex data operations.

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

Query Optimization and Evaluation 1 - Output Size Bounds and Information Theory

Explore output size bounds and information theory in query optimization, focusing on advanced techniques for efficient database management and AI applications.

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

Theoretical and Practical Insights from Linear Transformers

Explore theoretical proofs and empirical observations on Linear Transformers, shedding light on their ability to learn in-context and optimize like full-fledged Transformers.

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

Beyond NTK- A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time

Explore mean-field analysis of neural networks, examining polynomial width, samples, and time beyond Neural Tangent Kernel (NTK) theory for advanced optimization and algorithm design.

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

Hitting the High-Dimensional Notes - An ODE for SGD Learning Dynamics in High-Dimensions

Explore stochastic optimization algorithms in high dimensions, analyzing dynamics and performance of SGD and momentum methods using a framework inspired by random matrix theory.

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