Leveraging tree automata approximation results for efficient sampling and counting...

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


Duration: 38:03
190 views
6

Marcelo Arenas (PUC Chile and RelationalAI)
https://simons.berkeley.edu/talks/marcelo-arenas-puc-chile-relationalai-2023-10-18
Probabilistic Circuits and Logic

Counting the number of satisfying assignments and sampling these assignments are two fundamental problems for Boolean circuits. Unfortunately, these problems are hard to solve, and even to approximate. On the other hand, the corresponding problems for tree automata have recently been proved to be efficiently approximable. In this talk, we will demonstrate how these results for tree automata can be leveraged to derive polynomial-time approximation algorithms for the counting and sampling problems for structured DNNF circuits.



Other Videos By Simons Institute for the Theory of Computing


2023-10-20On Finding Modes of Gaussian Sum-Product Networks
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


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