5 papers
Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity
Hubie Chen, Stefan Mengel
A central computational task in database theory, finite model theory, and computer science at large is the evaluation of a first-order sentence on a finite structure. In the contex…
A canonical generalization of OBDD
Florent Capelli, YooJung Choi, Stefan Mengel +2
We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. They can be seen as a restriction of structured d-DNNF; that is, d-DNNF that respe…
Sum of Squares Circuits
Lorenzo Loconte, Stefan Mengel, Antonio Vergari
Designing expressive generative models that support exact and efficient inference is a core question in probabilistic ML. Probabilistic circuits (PCs) offer a framework where this…
A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity
Stefan Mengel, Harry Vinall-Smeeth
Motivated by recent connections to factorised databases, we analyse the efficiency of representations by context free grammars (CFGs). Concretely, we prove a recent conjecture by K…
Learning Model Agnostic Explanations via Constraint Programming
Frederic Koriche, Jean-Marie Lagniez, Stefan Mengel +1
Interpretable Machine Learning faces a recurring challenge of explaining the predictions made by opaque classifiers such as ensemble models, kernel methods, or neural networks in t…