research
∙
09/29/2022
Enumerating Regular Languages in Constant Delay
We study the task, for a given language L, of enumerating the (generally...
share
research
∙
05/02/2022
Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
We consider a weighted counting problem on matchings, denoted PrMatching...
research
∙
12/16/2021
Computing the Shapley Value of Facts in Query Answering
The Shapley value is a game-theoretic notion for wealth distribution tha...
research
∙
04/16/2021
On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results
In Machine Learning, the 𝖲𝖧𝖠𝖯-score is a version of the Shapley value th...
research
∙
11/12/2020
The Complexity of Counting Problems over Incomplete Databases
We study the complexity of various fundamental counting problems that ar...
research
∙
10/23/2020
Model Interpretability through the Lens of Computational Complexity
In spite of several claims stating that some models are more interpretab...
research
∙
07/28/2020
The Tractability of SHAP-scores over Deterministic and Decomposable Boolean Circuits
Scores based on Shapley values are currently widely used for providing e...
research
∙
12/26/2019
Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases
We consider the problem of exact probabilistic inference for Union of Co...
research
∙
12/23/2019
Towards Deterministic Decomposable Circuits for Safe Queries
There exist two approaches for exact probabilistic inference of UCQs on ...
research
∙
12/23/2019
Counting Problems over Incomplete Databases
We study the complexity of various fundamental counting problems that ar...
research
∙
11/07/2018
Connecting Knowledge Compilation Classes and Width Parameters
The field of knowledge compilation establishes the tractability of many ...
research
∙
08/14/2018
Evaluating Datalog via Tree Automata and Cycluits
We investigate parameterizations of both database instances and queries ...
research
∙
09/18/2017
Connecting Width and Structure in Knowledge Compilation (Extended Version)
Several query evaluation tasks can be done via knowledge compilation: th...
research
∙
09/18/2017
