We determine the exact freezing threshold, r^f, for a family of models of random boolean constraint satisfaction problems, including NAE-SAT and hypergraph 2-colouring, when the constraint size is sufficiently large. If the constraint-density of a random CSP, F, in our family is greater than r^f then for almost every solution of F, a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations in which we change o(n) variables at a time, always switching to another solution. If the constraint-density is less than r^f, then almost every solution has o(n) frozen variables. Freezing is a key part of the clustering phenomenon that is hypothesized by non-rigorous techniques from statistical physics. The understanding of clustering has led to the development of advanced heuristics such as Survey Propogation. It has been suggested that the freezing threshold is a precise algorithmic barrier: that for densities below r^f the random CSPs can be solved using very simple algorithms, while for densities above r^f one requires more sophisticated techniques in order to deal with frozen clusters.
@cite_46 @cite_39 @cite_11 establish the existence of what they call cluster-regions for @math -SAT, @math -COL, @math -NAE-SAT and hypergraph 2-colouring . @cite_39 proves that by the time the density exceeds @math times the hypothesized clustering threshold the solution space w.h.p. shatters into an exponential number of @math -separated cluster-regions, each containing an exponential number of solutions. While these cluster-regions are not shown to be well-connected, the well-connected property does not seem to be crucial to the difficulties that clusters pose for algorithms. So this was a very big step towards explaining why an algorithmic barrier seems to arise asymptotically (in @math ) close to the clustering threshold.
@cite_46 @cite_11 @cite_39
2088419249 1985875030 2128738155 179407972
Many NP-complete constraint satisfaction problems appear to undergo a “phase transition” from solubility to insolubility when the constraint density passes through a critical threshold. In all such cases it is easy to derive upper bounds on the location of the threshold by showing that above a certain density the first moment (expectation) of the number of solutions tends to zero. We show that in the case of certain symmetric constraints, considering the second moment of the number of solutions yields nearly matching lower bounds for the location of the threshold. Specifically, we prove that the threshold for both random hypergraph 2-colorability (Property B) and random Not-All-Equal @math -SAT is @math . As a corollary, we establish that the threshold for random @math -SAT is of order @math , resolving a long-standing open problem. We consider the following general correlation-clustering problem [N. Bansal, A. Blum, S. Chawla, Correlation clustering, in: Proc. 43rd Annu. IEEE Symp. on Foundations of Computer Science, Vancouver, Canada, November 2002, pp. 238-250]: given a graph with real nonnegative edge weights and a 〈+〉 〈-〉 edge labelling, partition the vertices into clusters to minimize the total weight of cut 〈+〉 edges and uncut 〈-〉 edges. Thus, 〈+〉 edges with large weights (representing strong correlations between endpoints) encourage those endpoints to belong to a common cluster while 〈-〉 edges with large weights encourage the endpoints to belong to different clusters. In contrast to most clustering problems, correlation clustering specifies neither the desired number of clusters nor a distance threshold for clustering; both of these parameters are effectively chosen to be best possible by the problem definition.Correlation clustering was introduced by [Correlation clustering, in: Proc. 43rd Annu. IEEE Syrup. on Foundations of Computer Science, Vancouver, Canada, November 2002, pp. 238-250], motivated by both document clustering and agnostic learning. They proved NP-hardness and gave constant-factor approximation algorithms for the special case in which the graph is complete (full information) and every edge has the same weight. We give an O(log n)-approximation algorithm for the general case based on a linear-programming rounding and the "region-growing" technique. We also prove that this linear program has a gap of Ω(log n), and therefore our approximation is tight under this approach. We also give an O(r3)-approximation algorithm for Kr, r-minor-free graphs. On the other hand, we show that the problem is equivalent to minimum multicut, and therefore APX-hard and difficult to approximate better than Θ(log n). We look at a model of random graphs suggested by Gilbert: given an integer @math and @math , scatter @math vertices independently and uniformly on a metric space, and then add edges connecting pairs of vertices of distance less than @math apart.We consider the asymptotics when the metric space is the interval [0, 1], and @math is a function of @math , for @math . We prove that every upwards closed property of (ordered) graphs has at least a weak threshold in this model on this metric space. (But we do find a metric space on which some upwards closed properties do not even have weak thresholds in this model.) We also prove that every upwards closed property with a threshold much above connectivity's threshold has a strong threshold. (But we also find a sequence of upwards closed properties with lower thresholds that are strictly weak.) We report on a novel technique called spatial coupling and its application in the analysis of random constraint satisfaction problems (CSP). Spatial coupling was invented as an engineering construction in the area of error correcting codes where it has resulted in efficient capacity-achieving codes for a wide range of channels. However, this technique is not limited to problems in communications, and can be applied in the much broader context of graphical models. We describe here a general methodology for applying spatial coupling to random constraint satisfaction problems and obtain lower bounds for their (rough) satisfiability threshold. The main idea is to construct a distribution of geometrically structured random K-SAT instances - namely the spatially coupled ensemble - which has the same (rough) satisfiability threshold, and is at the same time algorithmically easier to solve. Then by running well-known algorithms on the spatially coupled ensemble we obtain a lower bound on the (rough) satisfiability threshold of the original ensemble. The method is versatile because one can choose the CSP, there is a certain amount of freedom in the construction of the spatially coupled ensemble, and also in the choice of the algorithm. In this work we focus on random K-SAT but we have also checked that the method is successful for Coloring, NAE-SAT and XOR-SAT. We choose Unit Clause propagation for the algorithm which is analyzed over the spatially coupled instances. For K = 3, for instance, our lower bound is equal to 3.67 which is better than the current bounds in the literature. Similarly, for graph 3-colorability we get a bound of 2.22 which is also better than the current bounds in the literature.