Simons Institute Courses

Memory-Regret Tradeoff for Online Learning

Explores algorithms for online learning with limited memory, improving memory-regret tradeoffs against oblivious and adaptive adversaries. Discusses new techniques and lower bounds in the experts problem.

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

Memory-Regret Tradeoff for Online Learning

Explore the balance between memory usage and regret minimization in online learning algorithms, examining theoretical foundations and practical implications.

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

Sketching Techniques for Kernel Density Estimation

Explore advanced sketching techniques for efficient kernel density estimation, focusing on algorithmic design and computational improvements in high-dimensional data analysis.

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

Fast Attention Requires Bounded Entries

Explore the relationship between fast attention mechanisms and bounded entries in machine learning, with insights from Josh Alman's research on sketching and algorithm design.

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

Randomized Embeddings and Neural Networks

Exploring connections between random embeddings and neural networks through convex analysis, focusing on ReLU networks, randomized algorithms, and their implications for training efficiency.

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

Capacity Analysis of Vector Symbolic Architectures

Explores representation capacities of vector symbolic architectures, analyzing their ability to perform symbolic tasks and comparing them to a novel Hopfield network variant.

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

Improved Frequency Estimation Algorithms With and Without Predictions

Explore advanced frequency estimation algorithms for data streams, including novel approaches outperforming classical methods and further improvements using heavy-hitter predictions.

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

Testing Positive Semidefiniteness and Eigenvalue Approximation

Explore efficient algorithms for testing positive semidefiniteness and approximating eigenvalues in large matrices, with insights from David Woodruff of Carnegie Mellon University.

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

Sketching and Projecting

Explore sketching and projecting methods for linear systems and linear discriminant analysis, focusing on stochastic gradient approaches to achieve efficient solutions with reduced computational burden.

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

A Near-Linear Time Algorithm for the Chamfer Distance

Explore a groundbreaking near-linear time algorithm for computing the Chamfer distance, a crucial metric in computer vision and image processing.

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

Robustness of Sketches to Adaptive Inputs

Explore the resilience of sketching algorithms against adaptive inputs, examining their effectiveness in dynamic data environments and algorithmic design.

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

A Simple -Approximation Adaptive Sketching Algorithm for Maximum Weighted Matching

Explore a simple algorithm for approximating weighted matching in graphs using adaptive sketching, featuring a primal-dual analysis and multiplicative weight update method.

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

Sketching Algorithms for Max-DICUT and Other CSPs

Explore algorithms for Maximum Directed Cut problem in graph theory, focusing on sketching techniques, space complexity, and applications to Constraint Satisfaction Problems.

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

Distributed Graph Techniques in the MPC Model

Explore advanced distributed graph algorithms in the Massively Parallel Computation model, focusing on efficiency and scalability for large-scale data processing.

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

Massively Parallel Evaluation of Relational Queries II

Explore advanced techniques for parallel processing of relational database queries, focusing on fine-grained complexity and efficient evaluation strategies.

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