Zobrazeno 1 - 10
of 19
pro vyhledávání: '"Butti, Silvia"'
A celebrated result of Hastad established that, for any constant $\varepsilon>0$, it is NP-hard to find an assignment satisfying a $(1/|G|+\varepsilon)$-fraction of the constraints of a given 3-LIN instance over an Abelian group $G$ even if one is pr
Externí odkaz:
http://arxiv.org/abs/2411.01630
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. We give a combinatorial characterization of a certain natural linear pr
Externí odkaz:
http://arxiv.org/abs/2401.16998
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 promise CSPs, we propose an algebraic framework for valued promise CSPs.
Externí odkaz:
http://arxiv.org/abs/2401.15186
Autor:
Barto, Libor, Butti, Silvia
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 (equivalent to the basic linear programming relaxation) if and only if it is so
Externí odkaz:
http://arxiv.org/abs/2205.04805
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 (also called model). We study a class of problems that generalizes th
Externí odkaz:
http://arxiv.org/abs/2205.04787
Autor:
Butti, Silvia1 (AUTHOR) silvia.butti@upf.edu, Dalmau, Víctor1 (AUTHOR)
Publikováno v:
Theory of Computing Systems. Aug2024, Vol. 68 Issue 4, p838-867. 30p.
Autor:
Butti, Silvia, Dalmau, Victor
Given a pair of graphs $\textbf{A}$ and $\textbf{B}$, the problems of deciding whether there exists either a homomorphism or an isomorphism from $\textbf{A}$ to $\textbf{B}$ have received a lot of attention. While graph homomorphism is known to be NP
Externí odkaz:
http://arxiv.org/abs/2107.02956
Autor:
Butti, Silvia, Dalmau, Victor
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 constraints are controlled by agents which communicate with each other
Externí odkaz:
http://arxiv.org/abs/2007.13594
Autor:
Butti, Silvia, Zivny, Stanislav
Publikováno v:
SIAM Journal on Discrete Mathematics 34(1) (2020) 825-842
A cut $\varepsilon$-sparsifier of a weighted graph $G$ is a re-weighted subgraph of $G$ of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of $\varepsilon$. Since their introduction by Bencz\'ur and Karger [STOC'9
Externí odkaz:
http://arxiv.org/abs/1901.00754
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.