Pablo Martínez-Naredo

dblp:415/0350 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2026
0009-0004-3985-0624ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Artificial intelligence and machine learning · 2 · 2 first-author · 2 since 2021Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2026 Shapley-Shubik Attribution from Minimal Subsets (Short Paper)
abstract
We address the problem of attributing responsibility to individual clauses for the unsatisfiability of a propositional formula. Recent work adopted the Shapley-Shubik power index, proposing a probabilistic approximation algorithm. However, although polynomial, the required number of SAT solver calls becomes impractical when the input formula is not easy to solve. In such cases, it is often possible to enumerate a partial set of minimal unsatisfiable subsets (MUSes) and minimal correction subsets (MCSes). In this paper, we demonstrate that these subsets can be leveraged to efficiently bound and approximate the Shapley-Shubik index. We introduce a framework that exploits the structural information provided by the available sets to derive useful attribution explanations.
Pablo Martínez-Naredo, Raúl Mencía, João Marques-Silva 0001, Carlos Mencía
SAT1
2025 Explanations of Unsatisfiability Beyond Minimal Subsets
Pablo Martínez-Naredo, Raúl Mencía, João Marques-Silva 0001, Carlos Mencía
JELIA (2)1