Simons Institute Courses

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

Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees - I

Explore efficient algorithms for accessing answers to unions of conjunctive queries, focusing on ideal time guarantees and fine-grained complexity in query evaluation.

• YouTube
• 1 hour 9 minutes
• On-Demand
• Free Video

Fine Grained Complexity

Explore fine-grained complexity theory, its applications in logic, and its role in query evaluation, offering insights into computational efficiency and algorithmic analysis.

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

Intermediate Relational Algorithm Design

Explore fine-grained complexity logic and query evaluation in relational algorithms, focusing on advanced techniques for optimizing database operations and query processing.

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

Introduction to Relational Algorithms

Explore fine-grained complexity, logic, and query evaluation in relational algorithms, focusing on advanced concepts and their applications in database systems.

• YouTube
• 1 hour 5 minutes
• On-Demand
• Free Video

Solving Marginal MAP Exactly by Probabilistic Circuit Transformations

Efficient marginal MAP solver for probabilistic circuits using iterative transformations and pruning, enabling exact solutions without search for decision-making problems.

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

Direct Access for Conjunctive Queries with Negation

Explores efficient direct access techniques for signed conjunctive queries, extending tractability results to queries with negative atoms using circuit-based approaches.

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

Factorized Databases

Explore compressed yet lossless representations of relational data, their efficient processing, and applications in algorithms, probabilistic databases, and in-database machine learning.

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

Leveraging Tree Automata Approximation Results for Efficient Sampling and Counting

Explore efficient approximation algorithms for counting and sampling satisfying assignments in structured DNNF circuits, leveraging recent tree automata results.

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

Efficient Enumeration Algorithms via Circuits

Explore efficient enumeration of satisfying assignments in circuits, with applications to logic queries and database theory. Learn about maintaining enumeration structures on dynamic data.

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

Weighted Model Integration

Explore advanced probabilistic inference in hybrid domains using Weighted Model Integration. Learn about solvers, tractability analysis, and applications in Bayesian deep learning.

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

An Approximate Skolem Function Counter

Explores an algorithm for counting Skolem functions in quantified Boolean formulas, addressing challenges in synthesis problems and providing PAC guarantees for approximate counting.

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

Subtractive Mixture Models: Representation and Learning

Exploring subtractive mixtures in probabilistic circuits: increased expressiveness, efficient learning, and inference for complex distributions. Theoretical and empirical advantages over traditional additive mixtures.

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

The Rise of Tractable Circuits - From Cryptography to Continuous Generative Models

Exploring tractable circuits' applications in cryptography and continuous generative models, showcasing advancements in neuro-symbolic approaches and probabilistic inference for AI reasoning.

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

Decision Diagrams for Efficient Inference and Optimization in Expressive Discrete-Continuous Domains

Explore extended algebraic decision diagrams (XADDs) for representing piecewise functions, enabling efficient computations and novel solutions in probabilistic inference, optimization, and decision-making.

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