Showing 2022Show all
2 papers · 1 filter
cs.DS2022
Weisfeiler-Leman Invariant Promise Valued CSPs
Libor Barto, Silvia Butti
In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivale…
cs.CC2022
Fixed-Template Promise Model Checking Problems
Kristina Asimi, Libor Barto, Silvia Butti
The fixed-template constraint satisfaction problem (CSP) can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure…