Simons Institute Courses

A Stochastic Newton Algorithm for Distributed Convex Optimization

Explore a novel stochastic Newton algorithm for distributed convex optimization, reducing communication rounds while maintaining performance. Gain insights into convergence guarantees and practical applications.

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

Exploiting Geometric Structure in Matrix-Valued Optimization

Explore geometric structures in matrix-valued optimization, focusing on novel techniques and applications in algorithm design for complex optimization problems.

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

Short-Flat Decompositions and Faster Algorithms for Linear Inverse Problems

Explore algorithmic applications of short-flat decompositions in solving undercomplete linear inverse problems, with focus on sparse recovery and low-rank matrix completion techniques.

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

Nash Social Welfare and A Tale of Mathematical Programs

Explore determinant maximization, its applications in machine learning and game theory, and techniques like matroid intersection methods for solving this abstract problem.

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

IPM and Nested Dissection for Planar and Separable LPs

Exploring efficient LP solvers using nested dissection in IPM framework for planar min-cost flow, multicommodity flow, low treewidth LPs, and separable LPs. Focuses on optimization techniques and algorithm design.

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

Randomized Linear Algebra for Interior Point Methods

Explore randomized linear algebra techniques for efficient interior point methods in linear programming, focusing on applications in data science and scientific computing.

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

Robust Gradient Descent - Agnostically Estimating an Unknown Affine Transformation

Polynomial-time algorithm for robust learning of unknown affine transformations in ICA, achieving optimal TV-distance recovery guarantees using Robust Gradient Descent and a new geometric certificate.

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

Insights from Engineering Sketches for Production and Using Sketches at Scale

Explore insights on engineering sketches for large-scale production, covering Yahoo's journey in developing and implementing sketching algorithms across multiple languages and platforms.

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

Error Correction for Streaming Messages

Explores error-resilient encoding for streaming data, enabling accurate sketch computation despite message corruption while maintaining efficiency in communication and space complexity.

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

Sublinear Time Eigenvalue Approximation via Random Sampling

Explore efficient algorithms for approximating eigenvalues of large matrices using random sampling techniques, with applications in data analysis and machine learning.

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

Streaming Lower Bounds for the Needle Problems

Exploring tight lower bounds for frequency estimation in random order data streams, focusing on the needle problem and its implications for streaming algorithm design.

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

Streaming Euclidean K-Median and K-Means With O-Log N Space

Innovative algorithm for Euclidean k-median and k-means clustering in data streams, achieving (1+ε)-approximation with significantly reduced memory usage, breaking long-standing space complexity barriers.

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

Pseudorandom Hashing for Space-Bounded Computation with Applications in Streaming

Explores a new pseudorandom generator for space-bounded computation, improving update time in streaming algorithms without sacrificing space. Applications in Fp estimation and CountSketch are discussed.

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

Resizable Sketches

Explore techniques for maintaining fixed accuracy in sketches while allowing size growth, addressing challenges in data stream processing and algorithm design.

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

A Simple Quantum Sketch With Applications to Graph Algorithms

Explore quantum sketching for set analysis and its applications in graph algorithms, including triangle counting and Max-Dicut, with potential for significant space efficiency gains.

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