Simons Institute Courses

Utilizing Structure in Combinatorial Solving and Reasoning

Efficient utilization of structure for combinatorial problem solving, focusing on treewidth measure and answer set programming. Explores runtime bounds, decomposition-guided reductions, and empirical results in hard reasoning modes.

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

Approximating the TV Distance Between Two Product Distributions

Explore techniques for approximating total variation distance between high-dimensional product distributions, including randomized coupling and deterministic sparsification methods.

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

Tractable Control for Autoregressive Language Generation

Explores using tractable probabilistic models to impose lexical constraints in autoregressive text generation, achieving state-of-the-art performance on constrained text generation benchmarks.

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

On Finding Modes of Gaussian Sum-Product Networks

Explore challenges and tractability of finding modes in Probabilistic Circuits, focusing on Gaussian Sum-Product Networks for machine learning tasks like structured prediction.

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

Marginal Determinism in Structured Decomposable Circuits

Explores marginal determinism in probabilistic circuits, introducing md-vtrees for structured decomposable PCs. Discusses tractability conditions, efficient algorithms, and applications to causal inference queries like backdoor adjustment.

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

Stable Matching by Optimal Transport

Explore matching models with aligned preferences, focusing on supply-demand imbalances in markets like organ donation. Learn about stability, fairness, and optimal transport connections in matching theory.

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

Revealed Preferences of One-Sided Matching

Explores testable implications of the core in exchange economies with unknown preferences, linking core concepts to competitive equilibrium and consumer demand through revealed preferences.

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

Strict Core Stability and Strategy-Proofness for Hedonic Games with Friend-Oriented Preferences

Explore hedonic coalition formation with friend-oriented preferences, examining strict core stability and strategy-proofness in the context of the strongly connected components mechanism.

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

Market Design for Priority-Based Assignment with Distributional Objectives

Explores axiomatic approach to resource allocation, balancing priorities and equity through type-specific reserves and quotas. Analyzes single-school admissions and multi-school scenarios using Deferred Acceptance mechanism.

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

Estimating Separable Matching Models

Explores methods for estimating separable matching models with transferable utility, focusing on minimum distance estimation and reformulation of the Choo and Siow model as a generalized linear model with two-way fixed effects.

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

The Intractability of Hylland-Zeckhauser and Its Aftermath

Explores the Hylland-Zeckhauser mechanism for allocating goods, its intractability, and recent developments in Nash bargaining-based alternatives, discussing implications and open problems in market design.

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

Endogenous Market Formation: Theory and Evidence from Chilean College Admissions

Explores how similarity in school quality and applicant coverage can lead to voluntary adoption of centralized matching in college admissions, benefiting students with limited resources.

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

Algorithmic Mechanism Design with Investment

Explore approximation algorithms for knapsack problems, focusing on allocation efficiency and investment incentives in mechanism design without confirming negative externalities.

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