Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userClusters of solutions and replica symmetry breaking in random k-satisfiability
161
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the set of solutions of random k-satisfiability formulae through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes into an exponential number of pure states (clusters). We refine substantially this picture by: (i) determining the precise location of the clustering transition; (ii) uncovering a second `condensation phase transition in the structure of the solution set for k larger or equal than 4. These results both follow from computing the large deviation rate of the internal entropy of pure states. From a technical point of view our main contributions are a simplified version of the cavity formalism for special values of the Parisi replica symmetry breaking parameter m (in particular for m=1 via a correspondence with the tree reconstruction problem) and new large-k expansions.
rate research
Read More
We prove the impossibility of recent attempts to decouple the Replica Symmetry Breaking (RSB) picture for finite-dimensional spin glasses from the existence of many thermodynamic (i.e., infinite-volume) pure states while preserving another signature RSB feature --- space filling relative domain walls between different finite-volume states. Thus revisions of the notion of pure states cannot shield the RSB picture from the internal contradictions that rule out its physical correctness in finite dimensions at low temperature in large finite volume.
The fully-connected Ising $p$-spin model has for $p >2$ a discontinuous phase transition from the paramagnetic phase to a stable state with one-step replica symmetry breaking (1RSB). However, simulations in three dimension do not look like these mean-field results and have features more like those which would arise with full replica symmetry breaking (FRSB). To help understand how this might come about we have studied in the fully connected $p$-spin model the state of two-step replica symmetry breaking (2RSB). It has a free energy degenerate with that of 1RSB, but the weight of the additional peak in $P(q)$ vanishes. We expect that the state with full replica symmetry breaking (FRSB) is also degenerate with that of 1RSB. We suggest that finite size effects will give a non-vanishing weight to the FRSB features, as also will fluctuations about the mean-field solution. Our conclusion is that outside the fully connected model in the thermodynamic limit, FRSB is to be expected rather than 1RSB.
We study the quantum version of the random $K$-Satisfiability problem in the presence of the external magnetic field $Gamma$ applied in the transverse direction. We derive the replica-symmetric free energy functional within static approximation and the saddle-point equation for the order parameter: the distribution $P[h(m)]$ of functions of magnetizations. The order parameter is interpreted as the histogram of probability distributions of individual magnetizations. In the limit of zero temperature and small transverse fields, to leading order in $Gamma$ magnetizations $m approx 0$ become relevant in addition to purely classical values of $m approx pm 1$. Self-consistency equations for the order parameter are solved numerically using Quasi Monte Carlo method for K=3. It is shown that for an arbitrarily small $Gamma$ quantum fluctuations destroy the phase transition present in the classical limit $Gamma=0$, replacing it with a smooth crossover transition. The implications of this result with respect to the expected performance of quantum optimization algorithms via adiabatic evolution are discussed. The replica-symmetric solution of the classical random $K$-Satisfiability problem is briefly revisited. It is shown that the phase transition at T=0 predicted by the replica-symmetric theory is of continuous type with atypical critical exponents.
Directed polymers on 1+1 dimensional lattices coupled to a heat bath at temperature $T$ are studied numerically for three ensembles of the site disorder. In particular correlations of the disorder as well as fractal patterning are considered. Configurations are directly sampled in perfect thermal equilibrium for very large system sizes with up to $N=L^2= 32768 times 32768 approx 10^{9}$ sites. The phase-space structure is studied via the distribution of overlaps and hierarchical clustering of configurations. One ensemble shows a simple behavior like a ferromagnet. The other two ensembles exhibit indications for complex behavior reminiscent of multiple replica-symmetry breaking. Also results for the ultrametricity of the phase space and the phase transition behavior of $P(q)$ when varying the temperature $T$ are studied. In total, the present model ensembles offer convenient numerical accesses to comprehensively studying complex behavior.
We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Renyi and regular random graphs and determine their asymptotic values for large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
