7 citations · 11 across the 6 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2024
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…
cs.CC2024
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…
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…