Probabilistic Circuits and Logic 2023
2023-10-16..2023-10-19
Berkeley, United States
as the organisers put it
This workshop will discuss the connection between logic and circuits. Topics of interests include logic-guided circuit construction, lower/upper bounds, as well as problems related to (approximate) model counting.
who it's for
knowledge compilation researchers, probabilistic database researchers, probabilistic inference engineers, algorithm designers for model counting, machine learning researchers working on probabilistic circuits, data engineers working on query evaluation, formal logic and finite model theory researchers
topics
OBDD size dichotomy for FO; deterministic decomposable circuits; weighted first-order model counting; pairwise XOR hashing for approximate counting; FPRAS for DNF and queries; epsilon-contamination credal sets; AND/OR multivalued decision diagrams; rank lower bounds for arithmetic circuits; enumeration from d-DNNF variants; factorized databases and constant-delay enumeration
| title | author | length |
|---|---|---|
| Compiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit | Dan Suciu | 49m |
Proves a concrete dichotomy: for universally quantified positive FO sentences the optimal OBDDs size is either polynomial in domain size n or exponential… | ||
| The Intensional-Extensional Problem in Probabilistic Databases | Mikael Monet | 38m |
Asks whether every safe UCQ whose PTIME proof uses inclusion–exclusion admits a polynomial-size knowledge compilation into deterministic decomposable circuits… | ||
| Model Counting Meets Distinct Estimation | Kuldeep Singh | 39m |
Shows a concrete recipe that translates streaming F0 sketches into model-counting procedures and back, replacing streams by Sol(phi) and sketches by… | ||
| Credal Models for Uncertainty and Logic Treatment | Cassio de Campos | 52m |
Argues that replacing single probabilities with credal sets (convex sets of distributions) lets models represent ignorance, partial specifications and logical… | ||
| AND/OR Search Spaces for Anytime Probabilistic Reasoning | Rina Dechter | 40m |
Connects AND/OR search graphs to arithmetic circuits and uses compiled, graph-guided heuristics to drive anytime algorithms for MAP, marginal MAP and partition… | ||
| First-Order Model Counting and Sampling | Ondrej Kuzelka | 37m |
Describes weighted first‑order model counting (WFOMC) and sampling (WFOMS) for the symmetric case and shows concrete algorithms: reduce richer fragments to… | ||
| Combined Approximations for Probabilistic Query Evaluation: An Intensional Approach | Timothy Van Bremen | 33m |
Claims a method to get combined FPRASes for probabilistic query evaluation by compiling query+instance into non-deterministic OBDD or structured DNNF and then… | ||
| Tractable Bounding of Counterfactual Queries by Knowledge Compilation | Alessandro Antonucci | 34m |
Claims that compiling a causal model once into a symbolic compilation (a single parameterized arithmetic circuit) lets EM-based bounding of partially… | ||
| Lower Bounds for Tractable Arithmetic Circuits | Alexis de Colnet | 43m |
Shows a concrete lower bound method: define a value matrix rank for any vtree‑induced balanced partition and prove that its rank lower bounds the number of… | ||
| Efficient Enumeration Algorithms via Circuits | Antoine Amarili | 44m |
Presents concrete algorithms that enumerate satisfying assignments of structured set-circuits (d-DNNF variants) with linear preprocessing and output-linear… | ||
| Leveraging tree automata approximation results for efficient sampling and counting... | Marcelo Arenas | 38m |
Claim: sharp TA admits an FPRAS and that polynomial-time approximation for counting and almost-uniform sampling on a widely used fragment—structured… | ||
| Factorized Databases | Ahmet Kara | 51m |
Factorized databases store join results as lossless algebraic expressions using union and product, letting joins be computed in time proportional to the input… | ||
| Direct Access for Conjunctive Queries with Negation | Florent Capelli, Oliver Irwin | 53m |
Direct access for conjunctive queries with negation becomes possible by compiling the query+database into an ordered decision circuit that is polynomial-size… | ||
| Solving Marginal MAP Exactly by Probabilistic Circuit Transformations | YooJung Choi | 37m |
Presents an exact marginal MAP solver that never performs search but iteratively transforms probabilistic circuits by alternating prune irrelevant edges and… | ||
| Decision Diagrams for Efficient Inference and Optimization in Expressive Discrete+Continuous Domains | Scott Sanner | 45m |
Extends the algebraic decision diagram to continuous variables as the extended ADD (XADD) and represents arbitrary piecewise polynomial functions, with… | ||
| The Rise of Tractable Circuits: From Cryptography to Continuous Generative Models | Robert Peharz | 44m |
Shows two concrete advances: compiled AES mixed-column into SDDs and multiplies those logic circuits with measured leakage models to do fast, (almost) exact… | ||
| Subtractive Mixture Models: Representation and Learning | Antonio Vergari | 52m |
Introduces subtractive mixtures by allowing negative mixture weights, then enforces non-negativity by squaring the circuit, producing squared nonmonotonic… | ||
| An Approximate Skolem Function Counter | Brendan Juba, Kuldeep S. Meel, Arijit Shaw | 30m |
An algorithm produces a PAC guaranteed multiplicative approximation to the log number of Skolem functions, using two exact #SAT calls and a linear number of… | ||
| Weighted Model Integration | Zhe Zeng | 48m |
Weighted Model Integration (WMI) extends weighted model counting to SMT with linear arithmetic and polynomial weights and comes with concrete solvers… | ||
| Marginal Determinism in Structured Decomposable Circuits | Benjie Wang | 43m |
Introduces md-vtrees, a vtree annotated with per-node support labels that syntactically guarantees which q‑sets are marginally deterministic for any structured… | ||
| On Finding Modes of Gaussian Sum-Product Networks | Denis Maua | 45m |
Shows a practical algorithm—modal EM / mean‑shift for Gaussian SPNs—that runs by propagating two arrays of per‑variable numerators and denominators up the… | ||
| Tractable Control for Autoregressive Language Generation | Honghua Zhang | 47m |
Proposes GeLaTo: distill GPT-2 Large into a tractable HMM PC to compute exact conditioning probabilities and enforce lexical constraints with 100% constraint… | ||
| Approximating the TV Distance Between Two Product Distributions | Weiming Feng | 44m |
Proves FPRAS and FPTAS for total variation between general product distributions, using a greedy coupling and a ratio random variable estimator: sample from a… | ||
| Utilizing Structure in Combinatorial Solving and Reasoning | Markus Hecher | 40m |
Shows that decomposition-guided reductions give tight treewidth bounds for answer set programming: upper bounds encode provability along a tree decomposition… | ||
| nothing matches | ||