Simons Institute Courses

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

Credal Models for Uncertainty and Logic Treatment

Explore credal models as a generalization of probability theory for handling uncertainty and logic in AI, enhancing reliability and trustworthiness in decision-making processes.

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

Model Counting Meets Distinct Estimation

Exploring connections between model counting and F0 estimation, revealing shared techniques and developing new algorithms for both fields through cross-domain insights.

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

The Intensional-Extensional Problem in Probabilistic Databases

Explores probabilistic query evaluation in databases, discussing safe queries, knowledge compilation methods, and a combinatorial conjecture for solving complex cases efficiently.

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

Compiling FO Sentences to Circuits - Upper Bounds and Lower Bounds on the Size of the Circuit

Explores compilation of Boolean formulas into circuits, focusing on provenance of FO sentences. Examines size complexity and limitations of various circuit types for model counting.

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

Lower Bounds for Tractable Arithmetic Circuits

Explores techniques for proving size lower bounds on tractable arithmetic circuits, focusing on structural restrictions and their impact on circuit complexity in probabilistic reasoning.

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

Tractable Bounding of Counterfactual Queries by Knowledge Compilation

Explores bounding partially identifiable queries in causal models using knowledge compilation, offering computational advantages for inference in Bayesian networks with shared structures.

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

Combined Approximations for Probabilistic Query Evaluation - An Intensional Approach

Explore innovative techniques for probabilistic query evaluation using combined approximations, focusing on an intensional approach to enhance efficiency and accuracy.

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

First-Order Model Counting and Sampling

Explores recent developments in weighted first-order model counting and sampling, discussing applications in combinatorics, probability theory, and potential for declarative frameworks in sampling combinatorial structures.

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

AND/OR Search Spaces for Anytime Probabilistic Reasoning

Explore anytime probabilistic reasoning using AND/OR search spaces, enhancing decision-making in uncertain environments with efficient algorithms.

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