166 citations · 587 across the 57 of their papers we have counts for
33 papers · 1 filter
Lucy: Think and Reason to Solve Text-to-SQL
Nina Narodytska, Shay Vargaftik
Large Language Models (LLMs) have made significant progress in assisting users to query databases in natural language. While LLM-based techniques provide state-of-the-art results o…
On Computing Probabilistic Abductive Explanations
Yacine Izza, Xuanxiang Huang, Alexey Ignatiev +3
The most widely studied explainable AI (XAI) approaches are unsound. This is the case with well-known model-agnostic explanation approaches, and it is also the case with approaches…
Eliminating The Impossible, Whatever Remains Must Be True
Jinqiang Yu, Alexey Ignatiev, Peter J. Stuckey +2
The rise of AI methods to make predictions and decisions has led to a pressing need for more explainable artificial intelligence (XAI) methods. One common approach for XAI is to pr…
Provably Precise, Succinct and Efficient Explanations for Decision Trees
Yacine Izza, Alexey Ignatiev, Nina Narodytska +2
Decision trees (DTs) embody interpretable classifiers. DTs have been advocated for deployment in high-risk applications, but also for explaining other complex classifiers. Neverthe…
Scalable Verification of GNN-based Job Schedulers
Haoze Wu, Clark Barrett, Mahmood Sharif +2
Recently, Graph Neural Networks (GNNs) have been applied for scheduling jobs over clusters, achieving better performance than hand-crafted heuristics. Despite their impressive perf…
Partial Queries for Constraint Acquisition
Christian Bessiere, Clement Carbonnel, Anton Dries +8
Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the us…
Abduction-Based Explanations for Machine Learning Models
Alexey Ignatiev, Nina Narodytska, Joao Marques-Silva
The growing range of applications of Machine Learning (ML) in a multitude of settings motivates the ability of computing small explanations for predictions made. Small explanations…
Automated Verification of Neural Networks: Advances, Challenges and Perspectives
Francesco Leofante, Nina Narodytska, Luca Pulina +1
Neural networks are one of the most investigated and widely used techniques in Machine Learning. In spite of their success, they still find limited application in safety- and secur…
The Complexity of Integer Bound Propagation
Lucas Bordeaux, George Katsirelos, Nina Narodytska +1
Bound propagation is an important Artificial Intelligence technique used in Constraint Programming tools to deal with numerical constraints. It is typically embedded within a searc…
Breaking Symmetry with Different Orderings
Nina Narodytska, Toby Walsh
We can break symmetry by eliminating solutions within each symmetry class. For instance, the Lex-Leader method eliminates all but the smallest solution in the lexicographical order…
A Social Welfare Optimal Sequential Allocation Procedure
Thomas Kalinowski, Nina Nardoytska, Toby Walsh
We consider a simple sequential allocation procedure for sharing indivisible items between agents in which agents take turns to pick items. Supposing additive utilities and indepen…
Coalitional Manipulation for Schulze's Rule
Serge Gaspers, Thomas Kalinowski, Nina Narodytska +1
Schulze's rule is used in the elections of a large number of organizations including Wikimedia and Debian. Part of the reason for its popularity is the large number of axiomatic pr…
How Hard Is It to Control an Election by Breaking Ties?
Nicholas Mattei, Nina Narodytska, Toby Walsh
We study the computational complexity of controlling the result of an election by breaking ties strategically. This problem is equivalent to the problem of deciding the winner of a…
The SeqBin Constraint Revisited
George Katsirelos, Nina Narodytska, Toby Walsh
We revisit the SeqBin constraint. This meta-constraint subsumes a number of important global constraints like Change, Smooth and IncreasingNValue. We show that the previously propo…
Eliminating the Weakest Link: Making Manipulation Intractable?
Jessica Davies, Nina Narodytska, Toby Walsh
Successive elimination of candidates is often a route to making manipulation intractable to compute. We prove that eliminating candidates does not necessarily increase the computat…
Combining Voting Rules Together
Nina Narodytska, Toby Walsh, Lirong Xia
We propose a simple method for combining together voting rules that performs a run-off between the different winners of each voting rule. We prove that this combinator has several…
The RegularGcc Matrix Constraint
Ronald de Haan, Nina Narodytska, Toby Walsh
We study propagation of the RegularGcc global constraint. This ensures that each row of a matrix of decision variables satisfies a Regular constraint, and each column satisfies a G…
Manipulation of Nanson's and Baldwin's Rules
Nina Narodytska, Toby Walsh, Lirong Xia
Nanson's and Baldwin's voting rules select a winner by successively eliminating candidates with low Borda scores. We show that these rules have a number of desirable computational…
Complexity of and Algorithms for Borda Manipulation
Jessica Davies, George Katsirelos, Nina Narodytska +1
We prove that it is NP-hard for a coalition of two manipulators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computational…
The AllDifferent Constraint with Precedences
Christian Bessiere, Nina Narodytska, Claude-Guy Quimper +1
We propose AllDiffPrecedence, a new global constraint that combines together an AllDifferent constraint with precedence constraints that strictly order given pairs of variables. We…
An Empirical Study of Borda Manipulation
Jessica Davies, George Katsirelos, Nina Narodystka +1
We study the problem of coalitional manipulation in elections using the unweighted Borda rule. We provide empirical evidence of the manipulability of Borda elections in the form of…
Decomposition of the NVALUE constraint
Christian Bessiere, George Katsirelos, Nina Narodytska +2
We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposi…
On The Complexity and Completeness of Static Constraints for Breaking Row and Column Symmetry
George Katsirelos, Nina Narodytska, Toby Walsh
We consider a common type of symmetry where we have a matrix of decision variables with interchangeable rows and columns. A simple and efficient method to deal with such row and co…
Propagating Conjunctions of AllDifferent Constraints
Christian Bessiere, George Katsirelos, Nina Narodytska +2
We study propagation algorithms for the conjunction of two AllDifferent constraints. Solutions of an AllDifferent constraint can be seen as perfect matchings on the variable/value…