The Experts below are selected from a list of 21285 Experts worldwide ranked by ideXlab platform
Lenka Zdeborova - One of the best experts on this subject based on the ideXlab platform.
-
hiding quiet solutions in random Constraint Satisfaction Problems
Physical Review Letters, 2009Co-Authors: Florent Krzakala, Lenka ZdeborovaAbstract:We study Constraint Satisfaction Problems on the so-called planted random ensemble. We show that for a certain class of Problems, e.g., graph coloring, many of the properties of the usual random ensemble are quantitatively identical in the planted random ensemble. We study the structural phase transitions and the easy-hard-easy pattern in the average computational complexity. We also discuss the finite temperature phase diagram, finding a close connection with the liquid-glass-solid phenomenology.
-
Constraint Satisfaction Problems with isolated solutions are hard
Journal of Statistical Mechanics: Theory and Experiment, 2008Co-Authors: Lenka Zdeborova, Marc MézardAbstract:We study the phase diagram and the algorithmic hardness of the random 'locked' Constraint Satisfaction Problems, and compare them to the commonly studied 'non-locked' Problems like satisfiability of Boolean formulae or graph coloring. The special property of the locked Problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked Problems particularly appealing from the mathematical point of view. On the other hand, we show empirically that the clustered phase of these Problems is extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/hard transition (for currently known algorithms) in the locked Problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really hard Constraint Satisfaction Problems.
-
Constraint Satisfaction Problems with isolated solutions are hard
Journal of Statistical Mechanics: Theory and Experiment, 2008Co-Authors: Lenka Zdeborova, Marc MézardAbstract:We study the phase diagram and the algorithmic hardness of the random `locked' Constraint Satisfaction Problems, and compare them to the commonly studied 'non-locked' Problems like satisfiability of boolean formulas or graph coloring. The special property of the locked Problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked Problems particularly appealing from the mathematical point of view. On the other hand we show empirically that the clustered phase of these Problems is extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/hard transition (for currently known algorithms) in the locked Problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really hard Constraint Satisfaction Problems.
-
phase transitions and computational difficulty in random Constraint Satisfaction Problems
arXiv: Computational Complexity, 2008Co-Authors: F Krząkala, Lenka ZdeborovaAbstract: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. 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.
Guilhem Semerjian - One of the best experts on this subject based on the ideXlab platform.
-
On the cavity method for decimated random Constraint Satisfaction Problems and the analysis of belief propagation guided decimation algorithms
Journal of Statistical Mechanics: Theory and Experiment, 2009Co-Authors: Federico Ricci-tersenghi, Guilhem SemerjianAbstract:We introduce a version of the cavity method for diluted mean-field spin models that allows the computation of thermodynamic quantities similar to the Franz–Parisi quenched potential in sparse random graph models. This method is developed in the particular case of partially decimated random Constraint Satisfaction Problems. This allows us to develop a theoretical understanding of a class of algorithms for solving Constraint Satisfaction Problems, in which elementary degrees of freedom are sequentially assigned according to the results of a message passing procedure (belief propagation). We confront this theoretical analysis with the results of extensive numerical simulations.
-
On the freezing of variables in random Constraint Satisfaction Problems
Journal of Statistical Physics, 2008Co-Authors: Guilhem SemerjianAbstract:The set of solutions of random Constraint Satisfaction Problems (zero energy groundstates of mean-field diluted spin glasses) undergoes several structural phase transitions as the amount of Constraints is increased. This set first breaks down into a large number of well separated clusters. At the freezing transition, which is in general distinct from the clustering one, some variables (spins) take the same value in all solutions of a given cluster. In this paper we study the critical behavior around the freezing transition, which appears in the unfrozen phase as the divergence of the sizes of the rearrangements induced in response to the modification of a variable. The formalism is developed on generic Constraint Satisfaction Problems and applied in particular to the random satisfiability of boolean formulas and to the coloring of random graphs. The computation is first performed in random tree ensembles, for which we underline a connection with percolation models and with the reconstruction problem of information theory. The validity of these results for the original random ensembles is then discussed in the framework of the cavity method.
-
On the Freezing of Variables in Random Constraint Satisfaction Problems
Journal of Statistical Physics, 2008Co-Authors: Guilhem SemerjianAbstract:The set of solutions of random Constraint Satisfaction Problems (zero energy groundstates of mean-field diluted spin glasses) undergoes several structural phase transitions as the amount of Constraints is increased. This set first breaks down into a large number of well separated clusters. At the freezing transition, which is in general distinct from the clustering one, some variables (spins) take the same value in all solutions of a given cluster. In this paper we introduce and study a message passing procedure that allows to compute, for generic Constraint Satisfaction Problems, the sizes of the rearrangements induced in response to the modification of a variable. These sizes diverge at the freezing transition, with a critical behavior which is also investigated in details. We apply the generic formalism in particular to the random satisfiability of boolean formulas and to the coloring of random graphs. The computation is first performed in random tree ensembles, for which we underline a connection with percolation models and with the reconstruction problem of information theory. The validity of these results for the original random ensembles is then discussed in the framework of the cavity method.
-
Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
arXiv: Artificial Intelligence, 2007Co-Authors: Andrea Montanari, Federico Ricci-tersenghi, Guilhem SemerjianAbstract:Message passing algorithms have proved surprisingly successful in solving hard Constraint Satisfaction Problems on sparse random graphs. In such applications, variables are fixed sequentially to satisfy the Constraints. Message passing is run after each step. Its outcome provides an heuristic to make choices at next step. This approach has been referred to as `decimation,' with reference to analogous procedures in statistical physics. The behavior of decimation procedures is poorly understood. Here we consider a simple randomized decimation algorithm based on belief propagation (BP), and analyze its behavior on random k-satisfiability formulae. In particular, we propose a tree model for its analysis and we conjecture that it provides asymptotically exact predictions in the limit of large instances. This conjecture is confirmed by numerical simulations.
Federico Riccitersenghi - One of the best experts on this subject based on the ideXlab platform.
-
boolean Constraint Satisfaction Problems for reaction networks
arXiv: Molecular Networks, 2013Co-Authors: A. Seganti, A. De Martino, Federico RiccitersenghiAbstract:We define and study a class of (random) Boolean Constraint Satisfaction Problems representing minimal feasibility Constraints for networks of chemical reactions. The Constraints we consider encode, respectively, for hard mass-balance conditions (where the consumption and production fluxes of each chemical species are matched) and for soft mass-balance conditions (where a net production of compounds is in principle allowed). We solve these Constraint Satisfaction Problems under the Bethe approximation and derive the corresponding Belief Propagation equations, that involve 8 different messages. The statistical properties of ensembles of random Problems are studied via the population dynamics methods. By varying a chemical potential attached to the activity of reactions, we find first order transitions and strong hysteresis, suggesting a non-trivial structure in the space of feasible solutions.
-
on the solution space geometry of random Constraint Satisfaction Problems
Random Structures and Algorithms, 2011Co-Authors: Dimitris Achlioptas, Amin Cojaoghlan, Federico RiccitersenghiAbstract:For various random Constraint Satisfaction Problems there is a significant gap between the largest Constraint density for which solutions exist and the largest density for which any polynomial time algorithm is known to find solutions. Examples of this phenomenon include random k-SAT, random graph coloring, and a number of other random Constraint Satisfaction Problems. To understand this gap, we study the structure of the solution space of random k-SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number of connected components and give quantitative bounds for the diameter, volume, and number.© 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 251–268, 2011 © 2011 Wiley Periodicals, Inc.
-
on the solution space geometry of random Constraint Satisfaction Problems
arXiv: Computational Complexity, 2006Co-Authors: Dimitris Achlioptas, Federico RiccitersenghiAbstract:For a large number of random Constraint Satisfaction Problems, such as random k-SAT and random graph and hypergraph coloring, there are very good estimates of the largest Constraint density for which solutions exist. Yet, all known polynomial-time algorithms for these Problems fail to find solutions even at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such Problems as Constraints are added. In particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results establish rigorously one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random Constraint Satisfaction Problems.
-
on the solution space geometry of random Constraint Satisfaction Problems
Symposium on the Theory of Computing, 2006Co-Authors: Dimitris Achlioptas, Federico RiccitersenghiAbstract:For a number of random Constraint Satisfaction Problems, such as random k-SAT and random graph/hypergraph coloring, there are very good estimates of the largest Constraint density for which solutions exist. Yet, all known polynomial-time algorithms for these Problems fail to find solutions even at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such Problems as Constraints are added. In particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results establish rigorously one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random Constraint Satisfaction Problems.
A G Steenbeek - One of the best experts on this subject based on the ideXlab platform.
-
a genetic local search algorithm for random binary Constraint Satisfaction Problems
ACM Symposium on Applied Computing, 2000Co-Authors: Elena Marchiori, A G SteenbeekAbstract:This paper introduces a genetic local search algorithm for bi nary Constraint Satisfaction Problems. The core of the algo rithm consists of an ad-hoc optimization procedure followed by the application of blind genetic operators. A standard set of benchmark instances is used in order to assess the performance of the algorithm. The results indicate that this apparently naive hybridation of a genetic algorithm with lo cal search yields a rather powerful heuristic algorithm for random binary Constraint Satisfaction Problems.
-
solving binary Constraint Satisfaction Problems using evolutionary algorithms with an adaptive fitness function
Parallel Problem Solving from Nature, 1998Co-Authors: Jano Van Hemert, A. E. Eiben, Elena Marchiori, A G SteenbeekAbstract:This paper presents a comparative study of Evolutionary Algorithms (EAs) for Constraint Satisfaction Problems (CSPs). We focus on EAs where fitness is based on penalization of Constraint violations and the penalties are adapted during the execution. Three different EAs based on this approach are implemented. For highly connected Constraint networks, the results provide further empirical support to the theoretical prediction of the phase transition in binary CSPs.
Jano Van Hemert - One of the best experts on this subject based on the ideXlab platform.
-
comparing classical methods for solving binary Constraint Satisfaction Problems with state of the art evolutionary computation
Lecture Notes in Computer Science, 2002Co-Authors: Jano Van HemertAbstract:Constraint Satisfaction Problems form a class of Problems that are generally computationally difficult and have been addressed with many complete and heuristic algorithms. We present two complete algorithms, as well as two evolutionary algorithms, and compare them on randomly generated instances of binary Constraint Satisfaction Problems. We find that the evolutionary algorithms are less effective than the classical techniques.
-
solving binary Constraint Satisfaction Problems using evolutionary algorithms with an adaptive fitness function
Parallel Problem Solving from Nature, 1998Co-Authors: Jano Van Hemert, A. E. Eiben, Elena Marchiori, A G SteenbeekAbstract:This paper presents a comparative study of Evolutionary Algorithms (EAs) for Constraint Satisfaction Problems (CSPs). We focus on EAs where fitness is based on penalization of Constraint violations and the penalties are adapted during the execution. Three different EAs based on this approach are implemented. For highly connected Constraint networks, the results provide further empirical support to the theoretical prediction of the phase transition in binary CSPs.
