Zobrazeno 1 - 10
of 1 140
pro vyhledávání: '"Živný, P."'
A celebrated result of Hastad established that, for any constant $\varepsilon>0$, it is NP-hard to find an assignment satisfying a $(1/|G|+\varepsilon)$-fraction of the constraints of a given 3-LIN instance over an Abelian group $G$ even if one is pr
Externí odkaz:
http://arxiv.org/abs/2411.01630
Autor:
Nakajima, Tamio-Vesa, Živný, Stanislav
A (multi)set of literals, called a clause, is strongly satisfied by an assignment if no literal evaluates to false. Finding an assignment that maximises the number of strongly satisfied clauses is NP-hard. We present a simple algorithm that finds, gi
Externí odkaz:
http://arxiv.org/abs/2409.07837
Autor:
Nakajima, Tamio-Vesa, Živný, Stanislav
Given a (multi)graph $G$ which contains a bipartite subgraph with $\rho$ edges, what is the largest triangle-free subgraph of $G$ that can be found efficiently? We present an SDP-based algorithm that finds one with at least $0.8823 \rho$ edges, thus
Externí odkaz:
http://arxiv.org/abs/2406.20069
Autor:
Ciardo, Lorenzo, Živný, Stanislav
We connect the mixing behaviour of random walks over a graph to the power of the local-consistency algorithm for the solution of the corresponding constraint satisfaction problem (CSP). We extend this connection to arbitrary CSPs and their promise va
Externí odkaz:
http://arxiv.org/abs/2406.19685
A linearly ordered (LO) $k$-colouring of a hypergraph assigns to each vertex a colour from the set $\{0,1,\ldots,k-1\}$ in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find
Externí odkaz:
http://arxiv.org/abs/2404.19556
Autor:
Bulatov, Andrei A., Živný, Stanislav
The Mermin-Peres magic square is a celebrated example of a system of Boolean linear equations that is not (classically) satisfiable but is satisfiable via linear operators on a Hilbert space of dimension four. A natural question is then, for what kin
Externí odkaz:
http://arxiv.org/abs/2404.11709
Autor:
Larrauri, Alberto, Živný, Stanislav
We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more restricted monoid exists. As a corollary, we obtain a complexity classific
Externí odkaz:
http://arxiv.org/abs/2402.08434
Autor:
Nakajima, Tamio-Vesa, Živný, Stanislav
Goemans and Williamson designed a 0.878-approximation algorithm for Max-Cut in undirected graphs [JACM'95]. Khot, Kindler, Mosel, and O'Donnel showed that the approximation ratio of the Goemans-Williamson algorithm is optimal assuming Khot's Unique G
Externí odkaz:
http://arxiv.org/abs/2402.07863
Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently promise CSPs, we propose an algebraic framework for valued promise CSPs.
Externí odkaz:
http://arxiv.org/abs/2401.15186
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem #UCQ(C) provides as input a UCQ Q in C and a database D and the proble
Externí odkaz:
http://arxiv.org/abs/2311.10634