Zobrazeno 1 - 10
of 206
pro vyhledávání: '"ORDYNIAK, SEBASTIAN"'
This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the prevalent black-box perception, our study focuses on models with transpar
Externí odkaz:
http://arxiv.org/abs/2407.15780
Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular. Interestingly, these problems can be equivalently formulated as clas
Externí odkaz:
http://arxiv.org/abs/2407.10699
Autor:
Eriksson, Leif, Lagerkvist, Victor, Osipov, George, Ordyniak, Sebastian, Panolan, Fahad, Rychlicki, Mateusz
The quantified Boolean formula (QBF) problem is an important decision problem generally viewed as the archetype for PSPACE-completeness. Many problems of central interest in AI are in general not included in NP, e.g., planning, model checking, and no
Externí odkaz:
http://arxiv.org/abs/2405.06485
A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are o
Externí odkaz:
http://arxiv.org/abs/2404.14087
Difference Logic (DL) is a fragment of linear arithmetics where atoms are constraints x+k <= y for variables x,y (ranging over Q or Z) and integer k. We study the complexity of deciding the truth of existential DL sentences. This problem appears in m
Externí odkaz:
http://arxiv.org/abs/2402.03273
We study two variants of the fundamental problem of finding a cluster in incomplete data. In the problems under consideration, we are given a multiset of incomplete $d$-dimensional vectors over the binary domain and integers $k$ and $r$, and the goal
Externí odkaz:
http://arxiv.org/abs/2312.07628
Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued and binary data. However, obtaining an (ideally concise) explanation via hypersphere classification
Externí odkaz:
http://arxiv.org/abs/2312.07103
We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a co
Externí odkaz:
http://arxiv.org/abs/2312.07043
Autor:
Dabrowski, Konrad K., Jonsson, Peter, Ordyniak, Sebastian, Osipov, George, Pilipczuk, Marcin, Sharma, Roohani
Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity, a natural task is to classify the parameterized complexity of MinCSP
Externí odkaz:
http://arxiv.org/abs/2305.13889
Autor:
Fichte, Johannes K., Ganian, Robert, Hecher, Markus, Slivovsky, Friedrich, Ordyniak, Sebastian
The QSAT problem, which asks to evaluate a quantified Boolean formula (QBF), is of fundamental interest in approximation, counting, decision, and probabilistic complexity and is also considered the prototypical PSPACEcomplete problem. As such, it has
Externí odkaz:
http://arxiv.org/abs/2304.13896