Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSandwiches for Promise Constraint Satisfaction
89
0
0.0
(
0
)
Added by
Peter Mayr
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Promise Constraint Satisfaction Problems (PCSP) were proposed recently by Brakensiek and Guruswami arXiv:1704.01937 as a framework to study approximations for Constraint Satisfaction Problems (CSP). Informally a PCSP asks to distinguish between whether a given instance of a CSP has a solution or not even a specified relaxation can be satisfied. All currently known tractable PCSPs can be reduced in a natural way to tractable CSPs. Barto arXiv:1909.04878 presented an example of a PCSP over Boolean structures for which this reduction requires solving a CSP over an infinite structure. We give a first example of a PCSP over Boolean structures which reduces to a tractable CSP over a structure of size $3$ but not smaller. Further we investigate properties of PCSPs that reduce to systems of linear equations or to CSPs over structures with semilattice or majority polymorphism.
rate research
Read More
We prove super-polynomial lower bounds on the size of linear programming relaxations for approximati
We review the understanding of the random constraint satisfaction problems, focusing on the q-coloring of large random graphs, that has been achieved using the cavity method of the physicists. We also discuss the properties of the phase diagram in temperature, the connections with the glass transition phenomenology in physics, and the related algorithmic issues.
We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $frac{1}{2} + Omega(1/sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a emph{quantum} algorithm to find an assignment satisfying a $frac{1}{2} + Omega(D^{-3/4})$ fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for triangle-free instances; i.e., an efficient algorithm that finds an assignment satisfying at least a $mu + Omega(1/sqrt{D})$ fraction of constraints, where $mu$ is the fraction that would be satisfied by a uniformly random assignment.
We introduce and study the random locked constraint satisfaction problems. When increasing the density of constraints, they display a broad clustered phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. We thus propose new benchmarks of really hard optimization problems and provide insight into the origin of their typical hardness.
Several algorithms for solving constraint satisfaction problems are based on survey propagation, a variational inference scheme used to obtain approximate marginal probability estimates for variable assignments. These marginals correspond to how frequently each variable is set to true among satisfying assignments, and are used to inform branching decisions during search; however, marginal estimates obtained via survey propagation are approximate and can be self-contradictory. We introduce a more general branching strategy based on streamlining constraints, which sidestep hard assignments to variables. We show that streamlined solvers consistently outperform decimation-based solvers on random k-SAT instances for several problem sizes, shrinking the gap between empirical performance and theoretical limits of satisfiability by 16.3% on average for k=3,4,5,6.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
