{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:42:18Z","timestamp":1723016538014},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>We consider the computational problem of finding a smallest local explanation (anchor) for classifying a given feature vector (example) by a black-box model.  After showing that the problem is NP-hard in general, we study various natural restrictions of the problem in terms of problem parameters to see whether these restrictions make the problem fixed-parameter tractable or not. We draw a detailed and systematic complexity landscape for combinations of parameters, including the size of the anchor, the size of the anchor's coverage, and parameters that capture structural aspects of the problem instance, including rank-width, twin-width, and maximum difference.<\/jats:p>","DOI":"10.24963\/ijcai.2023\/369","type":"proceedings-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:30Z","timestamp":1691742690000},"page":"3312-3320","source":"Crossref","is-referenced-by-count":0,"title":["The Parameterized Complexity of Finding Concise Local Explanations"],"prefix":"10.24963","author":[{"given":"Sebastian","family":"Ordyniak","sequence":"first","affiliation":[{"name":"University of Leeds"}]},{"given":"Giacomo","family":"Paesani","sequence":"additional","affiliation":[{"name":"University of Leeds"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[{"name":"TU Wien"}]}],"member":"10584","event":{"number":"32","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2023","name":"Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}","start":{"date-parts":[[2023,8,19]]},"theme":"Artificial Intelligence","location":"Macau, SAR China","end":{"date-parts":[[2023,8,25]]}},"container-title":["Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:47:10Z","timestamp":1691743630000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2023\/369"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2023\/369","relation":{},"subject":[],"published":{"date-parts":[[2023,8]]}}}