Zobrazeno 1 - 10
of 259
pro vyhledávání: '"ORDYNIAK, SEBASTIAN"'
Autor:
Dabrowski, Konrad K., Jonsson, Peter, Ordyniak, Sebastian, Osipov, George, Wahlstroem, Magnus
We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate within any constan
Externí odkaz:
http://arxiv.org/abs/2410.09932
Autor:
Da Lozzo, Giordano, Ganian, Robert, Gupta, Siddharth, Mohar, Bojan, Ordyniak, Sebastian, Zehavi, Meirav
We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an $n$-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertice
Externí odkaz:
http://arxiv.org/abs/2409.19410
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