38 citations · 99 across the 20 of their papers we have counts for
27 papers
Graphs with Bounded Push-Pop Walk Orderings
Antoine Amarilli, Claire David, Nadime Francis +3
Consider a directed graph G and the (generally infinite) set Walks(G) of the walks in that graph. We are interested in ordering Walks(G) as w1, w2,... in a way that ensures that ea…
Path Length Existence Problems in Bounded-Treewidth Probabilistic Graphs
Antoine Amarilli, Mikaël Monet, Harshul Sagar
We consider the problem of computing the probability of existence of a source-to-target path or walk satisfying a given length constraint in an input probabilistic graph. The lengt…
The S-Hamiltonian Cycle Problem
Antoine Amarilli, Arthur Lombardo, Mikaël Monet
Determining if an input undirected graph is Hamiltonian, i.e., if it has a cycle that visits every vertex exactly once, is one of the most famous NP-complete problems. We consider…
Gray Codes With Constant Delay and Constant Auxiliary Space
Antoine Amarilli, Claire David, Nadime Francis +3
We give the first two algorithms to enumerate all binary words of (like Gray codes) while ensuring that the delay and the auxiliary space is independent from ,…
Locality Testing for NFAs is PSPACE-complete
Antoine Amarilli, Mikaël Monet, Rémi De Pretto
The class of local languages is a well-known subclass of the regular languages that admits many equivalent characterizations. In this short note we establish the PSPACE-completenes…
Confluence of the Node-Domination and Edge-Domination Hypergraph Rewrite Rules
Antoine Amarilli, Mikaël Monet, Rémi De Pretto
In this note, we study two rewrite rules on hypergraphs, called edge-domination and node-domination, and show that they are confluent. These rules are rather natural and commonly u…
On the Complexity of Language Membership for Probabilistic Words
Antoine Amarilli, Mikaël Monet, Paul Raphaël +1
We study the membership problem to context-free languages (CFLs) on probabilistic words, that specify for each position a probability distribution on the letters. Our task is to co…
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…
A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata
Antoine Amarilli, Marcelo Arenas, YooJung Choi +3
This document is an introduction to two related formalisms to define Boolean functions: binary decision diagrams, and Boolean circuits. It presents these formalisms and several of…
The Non-Cancelling Intersections Conjecture
Antoine Amarilli, Mikaël Monet, Dan Suciu
In this note, we present a conjecture on intersections of set families, and a rephrasing of the conjecture in terms of principal downsets of Boolean lattices. The conjecture inform…
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…
Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
Antoine Amarilli, Mikaël Monet
We consider a weighted counting problem on matchings, denoted , on an arbitrary fixed graph family . The input consists of a graph $G…
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…
Model Interpretability through the Lens of Computational Complexity
Pablo Barceló, Mikaël Monet, Jorge Pérez +1
In spite of several claims stating that some models are more interpretable than others -- e.g., "linear models are more interpretable than deep neural networks" -- we still lack a…
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…
The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits
Marcelo Arenas, Pablo Barceló Leopoldo Bertossi, Mikaël Monet
Scores based on Shapley values are widely used for providing explanations to classification results over machine learning models. A prime example of this is the influential SHAP-sc…
Towards Deterministic Decomposable Circuits for Safe Queries
Mikaël Monet, Dan Olteanu
There exist two approaches for exact probabilistic inference of UCQs on tuple-independent databases. In the extensional approach, query evaluation is performed within a DBMS by exp…
Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases
Mikaël Monet
We consider the problem of exact probabilistic inference for Union of Conjunctive Queries (UCQs) on tuple-independent databases. For this problem, two approaches currently coexist.…
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…
Connecting Knowledge Compilation Classes and Width Parameters
Antoine Amarilli, Florent Capelli, Mikaël Monet +1
The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structure…
Evaluating Datalog via Tree Automata and Cycluits
Antoine Amarilli, Pierre Bourhis, Mikaël Monet +1
We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We show that clique-frontier-gu…
Connecting Width and Structure in Knowledge Compilation (Extended Version)
Antoine Amarilli, Mikaël Monet, Pierre Senellart
Several query evaluation tasks can be done via knowledge compilation: the query result is compiled as a lineage circuit from which the answer can be determined. For such tasks, it…