38 citations · 63 across the 11 of their papers we have counts for
8 papers · 1 filter
Resilience for Regular Path Queries: Towards a Complexity Classification
Antoine Amarilli, Wolfgang Gatterbauer, Neha Makhija +2
The resilience problem for a query and an input set or bag database is to compute the minimum number of facts to remove from the database to make the query false. In this paper, we…
The Shapley Value in Database Management
Leopoldo Bertossi, Benny Kimelfeld, Ester Livshits +1
Attribution scores can be applied in data management to quantify the contribution of individual items to conclusions from the data, as part of the explanation of what led to these…
Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
Pratik Karmakar, Mikaël Monet, Pierre Senellart +1
Shapley values, originating in game theory and increasingly prominent in explainable AI, have been proposed to assess the contribution of facts in query answering over databases, a…
Ranked Enumeration for MSO on Trees via Knowledge Compilation
Antoine Amarilli, Pierre Bourhis, Florent Capelli +1
We study the problem of enumerating the satisfying assignments for circuit classes from knowledge compilation, where assignments are ranked in a specific order. In particular, we s…
Computing the Shapley Value of Facts in Query Answering
Daniel Deutch, Nave Frost, Benny Kimelfeld +1
The Shapley value is a game-theoretic notion for wealth distribution that is nowadays extensively used to explain complex data-intensive computation, for instance, in network analy…
The Complexity of Counting Problems over Incomplete Databases
Marcelo Arenas, Pablo Barceló, Mikaël Monet
We study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in th…