38 citations · 73 across the 10 of their papers we have counts for
11 papers
ExplAIner: A Declarative Query Language for Explaining Classification Models
Marcelo Arenas, Pablo Barceló, Diego Bustamante +3
The XAI community has studied a wide range of queries and scores for explaining predictions of ML models. From a data management perspective, this proliferation of explanation noti…
On the Complexity of Counting Orderings in Graphs
Marcelo Arenas, María Alejandra Schild, Bernardo Subercaseaux
We study the computational complexity of several counting problems on graphs. Each of these problems consists of counting orderings of the vertices or edges with adjacency constrai…
Probabilistic Explanations for Linear Models
Bernardo Subercaseaux, Marcelo Arenas, Kuldeep S Meel
Formal XAI is an emerging field that focuses on providing explanations with mathematical guarantees for the decisions made by machine learning models. A significant amount of work…
A Uniform Language to Explain Decision Trees
Marcelo Arenas, Pablo Barcelo, Diego Bustamante +2
The formal XAI community has studied a plethora of interpretability queries aiming to understand the classifications made by decision trees. However, a more uniform understanding o…
The Packing Chromatic Number of the Infinite Square Grid is 15
Bernardo Subercaseaux, Marijn J. H. Heule
A packing -coloring is a natural variation on the standard notion of graph -coloring, where vertices are assigned numbers from , and any two vertices assign…
On Computing Probabilistic Explanations for Decision Trees
Marcelo Arenas, Pablo Barceló, Miguel Romero +1
Formal XAI (explainable AI) is a growing area that focuses on computing explanations with mathematical guarantees for the decisions made by ML models. Inside formal XAI, one of the…
Wordle is NP-hard
Daniel Lokshtanov, Bernardo Subercaseaux
Wordle is a single-player word-guessing game where the goal is to discover a secret word that has been chosen from a dictionary . In order to discover , the player can ma…
Foundations of Symbolic Languages for Model Interpretability
Marcelo Arenas, Daniel Baez, Pablo Barceló +2
Several queries and scores have recently been proposed to explain individual predictions over ML models. Given the need for flexible, reliable, and easy-to-apply interpretability m…
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 Computational Complexity of Evil Hangman
Jérémy Barbay, Bernardo Subercaseaux
The game of Hangman is a classical asymmetric two player game in which one player, the setter, chooses a secret word from a language, that the other player, the guesser, tries to d…
On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra
Pablo Barceló, Nelson Higuera, Jorge Pérez +1
We study the expressive power of the LARA language -- a recently proposed unified model for expressing relational and linear algebra operations -- both in terms of traditional data…