7 citations · 7 across the 2 of their papers we have counts for
5 papers
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…
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…
Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
Silvia Butti, Victor Dalmau
Given a pair of graphs and , the problems of deciding whether there exists either a homomorphism or an isomorphism from to have r…
The Complexity of the Distributed Constraint Satisfaction Problem
Silvia Butti, Victor Dalmau
We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and…
Sparsification of Binary CSPs
Silvia Butti, Stanislav Zivny
A cut -sparsifier of a weighted graph is a re-weighted subgraph of of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of $…