1 citations · 1 across the 4 of their papers we have counts for
6 papers
Constant-factor approximation of MinCostCSP with a conservative majority polymorphism
Marcin Kozik, Stanislav Živný
For a relational structure A, the Minimum Cost Constraint Satisfaction Problem is the following problem denoted by MinCostCSP(A): Given an instance of CSP(A) with rational costs on…
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa +1
We introduce a new notion of sparsification, called \emph{strong sparsification}, in which constraints are not removed but variables can be merged. As our main result, we present a…
Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna +1
Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmo…
Maximum And- vs. Even-SAT
Tamio-Vesa Nakajima, Stanislav Živný
A multiset of literals, called a clause, is \emph{strongly satisfied} by an assignment if \emph{no} literal evaluates to false. Finding an assignment that maximises the number of s…
A Dichotomy for Maximum PCSPs on Graphs
Tamio-Vesa Nakajima, Stanislav Živný
Fix two non-empty loopless graphs and such that maps homomorphically to . The Maximum Promise Constraint Satisfaction Problem parameterised by and is the fol…
The periodic structure of local consistency
Lorenzo Ciardo, Stanislav Živný
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 (…