5 papers
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…
A Dichotomy for Maximum PCSPs on Graphs
Tamio-Vesa Nakajima, Stanislav Živný, 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…
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…
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 (…