1 citations · 1 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
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…
cs.DS2024
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…
cs.DS2024
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…