7 citations · 11 across the 6 of their papers we have counts for
8 papers
Optimal Inapproximability of Promise Equations over Finite Groups
Silvia Butti, Alberto Larrauri, Stanislav Živný
A celebrated result of Hastad established that, for any constant , it is NP-hard to find an assignment satisfying a -fraction of the constraints…
The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
Libor Barto, Silvia Butti, Víctor Dalmau
In this paper we study the interactions between so-called fractional relaxations of the integer programs (IPs) which encode homomorphism and isomorphism of relational structures. W…
The Rise of Plurimorphisms: Algebraic Approach to Approximation
Libor Barto, Silvia Butti, Alexandr Kazda +2
Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently pro…
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 $…