Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFrom Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
112
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a methodology for generating Ising Hamiltonians of tunable complexity and with a priori known ground states based on a decomposition of the model graph into edge-disjoint subgraphs. The idea is illustrated with a spin-glass model defined on a cubic lattice, where subproblems, whose couplers are restricted to the two values {-1,+1}, are specified on unit cubes and are parametrized by their local degeneracy. The construction is shown to be equivalent to a type of three-dimensional constraint satisfaction problem known as the tiling puzzle. By varying the proportions of subproblem types, the Hamiltonian can span a dramatic range of typical computational complexity, from fairly easy to many orders of magnitude more difficult than prototypical bimodal and Gaussian spin glasses in three space dimensions. We corroborate this behavior via experiments with different algorithms and discuss generalizations and extensions to different types of graphs.
rate research
Read More
The typical complexity of Constraint Satisfaction Problems (CSPs) can be investigated by means of random ensembles of instances. The latter exhibit many threshold phenomena besides their satisfiability phase transition, in particular a clustering or dynamic phase transition (related to the tree reconstruction problem) at which their typical solutions shatter into disconnected components. In this paper we study the evolution of this phenomenon under a bias that breaks the uniformity among solutions of one CSP instance, concentrating on the bicoloring of k-uniform random hypergraphs. We show that for small k the clustering transition can be delayed in this way to higher density of constraints, and that this strategy has a positive impact on the performances of Simulated Annealing algorithms. We characterize the modest gain that can be expected in the large k limit from the simple implementation of the biasing idea studied here. This paper contains also a contribution of a more methodological nature, made of a review and extension of the methods to determine numerically the discontinuous dynamic transition threshold.
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.
We study numerically the nonequilibrium dynamics of the Ising Spin Glass, for a time that spans eleven orders of magnitude, thus approaching the experimentally relevant scale (i.e. {em seconds}). We introduce novel analysis techniques that allow to compute the coherence length in a model-independent way. Besides, we present strong evidence for a replicon correlator and for overlap equivalence. The emerging picture is compatible with non-coarsening behavior.
Random Constraint Satisfaction Problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information theoretic problem called tree reconstruction. In this article we study this threshold for two CSPs, namely the bicoloring of $k$-uniform hypergraphs with a density $alpha$ of constraints, and the $q$-coloring of random graphs with average degree $c$. We show that in the large $k,q$ limit the clustering transition occurs for $alpha = frac{2^{k-1}}{k} (ln k + ln ln k + gamma_{rm d} + o(1))$, $c= q (ln q + ln ln q + gamma_{rm d}+ o(1))$, where $gamma_{rm d}$ is the same constant for both models. We characterize $gamma_{rm d}$ via a functional equation, solve the latter numerically to estimate $gamma_{rm d} approx 0.871$, and obtain an analytic lowerbound $gamma_{rm d} ge 1 + ln (2 (sqrt{2}-1)) approx 0.812$. Our analysis unveils a subtle interplay of the clustering transition with the rigidity (naive reconstruction) threshold that occurs on the same asymptotic scale at $gamma_{rm r}=1$.
We investigate the clustering transition undergone by an exemplary random constraint satisfaction problem, the bicoloring of $k$-uniform random hypergraphs, when its solutions are weighted non-uniformly, with a soft interaction between variables belonging to distinct hyperedges. We show that the threshold $alpha_{rm d}(k)$ for the transition can be further increased with respect to a restricted interaction within the hyperedges, and perform an asymptotic expansion of $alpha_{rm d}(k)$ in the large $k$ limit. We find that $alpha_{rm d}(k) = frac{2^{k-1}}{k}(ln k + ln ln k + gamma_{rm d} + o(1))$, where the constant $gamma_{rm d}$ is strictly larger than for the uniform measure over solutions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
