Efficient Enumeration Algorithms via Circuits

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=CMTgtDlGDI8


Duration: 44:27
280 views
9

Antoine Amarili (Telecom Paris)
https://simons.berkeley.edu/talks/antoine-amarili-telecom-paris-2023-10-18
Probabilistic Circuits and Logic

This talk will present our results on how to efficiently enumerate the satisfying assignments of circuits in tractable knowledge compilation formalisms (structured d-DNNFs and variants). We will explain how these results can then be used to re-prove linear-preprocessing and output-linear delay enumeration of the satisfying assignments of Monadic Second-Order logic queries on trees, or the enumeration of the mappings of document spanners in database theory. We will also explain how these results allow for efficient updates to the underlying circuit, leading to results on efficiently maintaining enumeration structures on dynamic data.



Other Videos By Simons Institute for the Theory of Computing


2023-10-20Marginal Determinism in Structured Decomposable Circuits
2023-10-19Weighted Model Integration
2023-10-19An Approximate Skolem Function Counter
2023-10-19Subtractive Mixture Models: Representation and Learning
2023-10-19The Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
2023-10-19Decision Diagrams for Efficient Inference and Optimization in Expressive Discrete+Continuous Domains
2023-10-18Solving Marginal MAP Exactly by Probabilistic Circuit Transformations
2023-10-18Direct Access for Conjunctive Queries with Negation
2023-10-18Factorized Databases
2023-10-18Leveraging tree automata approximation results for efficient sampling and counting...
2023-10-18Efficient Enumeration Algorithms via Circuits
2023-10-17Lower Bounds for Tractable Arithmetic Circuits
2023-10-17Tractable Bounding of Counterfactual Queries by Knowledge Compilation
2023-10-17Combined Approximations for Probabilistic Query Evaluation: An Intensional Approach
2023-10-17First-Order Model Counting and Sampling
2023-10-17AND/OR Search Spaces for Anytime Probabilistic Reasoning
2023-10-17Credal Models for Uncertainty and Logic Treatment
2023-10-16Model Counting Meets Distinct Estimation
2023-10-16The Intensional-Extensional Problem in Probabilistic Databases
2023-10-16Compiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit
2023-10-13Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Probabilistic Circuits and Logic
Antoine Amarili