Solution clustering in random satisfiability

For a large number of random constraint satisfaction problems, such as random k-SAT and random graph and hypergraph coloring, we have very good estimates of the largest constraint density for which solutions exist. All known polynomial-time algorithms for these problems, though, fail to find solutions 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 show that in random k-SAT for k ≥ 8, 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.     

A residual-based message passing algorithm for constraint satisfaction problems

Message passing algorithms, whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages, provide a powerful toolkit in tackling hard computational tasks in optimization, inference, and learning problems. In the context of constraint satisfaction problems (CSPs), when a control parameter (such as constraint density) is tuned, multiple threshold phenomena emerge, signaling fundamental structural transitions in their solution space. Finding solutions around these transition points is exceedingly challenging for algorithm design, where message passing algorithms suffer from a large message fluctuation far from convergence. Here we introduce a residual-based updating step into message passing algorithms, in which messages with large variation between consecutive steps are given high priority in the updating process. For the specific example of model RB (revised B), a typical prototype of random CSPs with growing domains, we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost. Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.     

Large Deviation Principles and Complete Equivalence and Nonequivalence Results for Pure and Mixed Ensembles

We consider a general class of statistical mechanical models of coherent structures in turbulence, which includes models of two-dimensional fluid motion, quasi-geostrophic flows, and dispersive waves. First, large deviation principles are proved for the canonical ensemble and the microcanonical ensemble. For each ensemble the set of equilibrium macrostates is defined as the set on which the corresponding rate function attains its minimum of 0. We then present complete equivalence and nonequivalence results at the level of equilibrium macrostates for the two ensembles. Microcanonical equilibrium macrostates are characterized as the solutions of a certain constrained minimization problem, while canonical equilibrium macrostates are characterized as the solutions of an unconstrained minimization problem in which the constraint in the first problem is replaced by a Lagrange multiplier. The analysis of equivalence and nonequivalence of ensembles reduces to the following question in global optimization. What are the relationships between the set of solutions of the constrained minimization problem that characterizes microcanonical equilibrium macrostates and the set of solutions of the unconstrained minimization problem that characterizes canonical equilibrium macrostates? In general terms, our main result is that a necessary and sufficient condition for equivalence of ensembles to hold at the level of equilibrium macrostates is that it holds at the level of thermodynamic functions, which is the case if and only if the microcanonical entropy is concave. The necessity of this condition is new and has the following striking formulation. If the microcanonical entropy is not concave at some value of its argument, then the ensembles are nonequivalent in the sense that the corresponding set of microcanonical equilibrium macrostates is disjoint from any set of canonical equilibrium macrostates. We point out a number of models of physical interest in which nonconcave microcanonical entropies arise. We also introduce a new class of ensembles called mixed ensembles, obtained by treating a subset of the dynamical invariants canonically and the complementary set microcanonically. Such ensembles arise naturally in applications where there are several independent dynamical invariants, including models of dispersive waves for the nonlinear Schrödinger equation. Complete equivalence and nonequivalence results are presented at the level of equilibrium macrostates for the pure canonical, the pure microcanonical, and the mixed ensembles.     

Locked constraint satisfaction problems

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.     

Landscape of solutions in constraint satisfaction problems

We present a theoretical framework for characterizing the geometrical properties of the space of solutions in constraint satisfaction problems, together with practical algorithms for studying this structure on particular instances. We apply our method to the coloring problem, for which we obtain the total number of solutions and analyze in detail the distribution of distances between solutions.     

Covariance Structure Behind Breaking of Ensemble Equivalence in Random Graphs

For a random graph subject to a topological constraint, the microcanonical ensemble requires the constraint to be met by every realisation of the graph (‘hard constraint’), while the canonical ensemble requires the constraint to be met only on average (‘soft constraint’). It is known that breaking of ensemble equivalence may occur when the size of the graph tends to infinity, signalled by a non-zero specific relative entropy of the two ensembles. In this paper we analyse a formula for the relative entropy of generic discrete random structures recently put forward by Squartini and Garlaschelli. We consider the case of a random graph with a given degree sequence (configuration model), and show that in the dense regime this formula correctly predicts that the specific relative entropy is determined by the scaling of the determinant of the matrix of canonical covariances of the constraints. The formula also correctly predicts that an extra correction term is required in the sparse regime and in the ultra-dense regime. We further show that the different expressions correspond to the degrees in the canonical ensemble being asymptotically Gaussian in the dense regime and asymptotically Poisson in the sparse regime (the latter confirms what we found in earlier work), and the dual degrees in the canonical ensemble being asymptotically Poisson in the ultra-dense regime. In general, we show that the degrees follow a multivariate version of the Poisson–Binomial distribution in the canonical ensemble.     

Phase diagram of random heteropolymers

We propose a new analytic approach to study the phase diagram of random heteropolymers, based on the cavity method. For copolymers we analyze the nature and phenomenology of the glass transition as a function of sequence correlations. Depending on these correlations, we find that two different scenarios for the glass transition can occur. We show that, beside the much studied possibility of an abrupt freezing transition at low temperature, the system can exhibit, upon cooling, a first transition to a soft glass phase with fully broken replica symmetry and a continuously growing degree of freezing as the temperature is lowered.     

Rigorous results in the mean-field theory of freezing

The mean-field theory of freezing, of which the Kirkwood-Monroe theory is a special case, is formulated in terms of a variational principle which can be derived from a statistical model. New upper and lower bounds on the free energy are found, and used to prove the existence of and to locate a freezing transition. The Kirkwood-Monroe theory is shown to obey a scaling law which implies that the freezing transition has no critical point and that the pressure-temperature phase diagram is a parabola. For a suitable choice of interaction potential, the free energy and density distribution of a crystalline state are calculated with very small error. The variational principle yields an integral equation found previously by van Kampen. This equation is derived rigorously, and shown to admit solutions of any chosen periodicity. The equation is transformed into a nonlinear integral equation of the Hammerstein type, and some standard uniqueness theorems applied. The equation is also transformed into a set of linear equations closely resembling the Kirkwood-Salsburg equations. Many unsolved problems are raised.     

Lossy data compression with random gates

We introduce a new protocol for a lossy data compression algorithm which is based on constraint satisfaction gates. We show that the theoretical capacity of algorithms built from standard parity-check gates converges exponentially fast to the Shannon's bound when the number of variables seen by each gate increases. We then generalize this approach by introducing random gates. They have theoretical performances nearly as good as parity checks, but they offer the great advantage that the encoding can be done in linear time using the survey inspired decimation algorithm, a powerful algorithm for constraint satisfaction problems derived from statistical physics.     

3D loop models and the CP(n-1) sigma model

Many statistical mechanics problems can be framed in terms of random curves; we consider a class of three-dimensional loop models that are prototypes for such ensembles. The models show transitions between phases with infinite loops and short-loop phases. We map them to CP(n-1) sigma models, where n is the loop fugacity. Using Monte Carlo simulations, we find continuous transitions for n=1, 2, 3, and first order transitions for n≥5. The results are relevant to line defects in random media, as well as to Anderson localization and (2+1)-dimensional quantum magnets.     

太赫兹波在亚波长随机金属Al颗粒中的相干传播

本文报道亚波长特征尺寸的随机金属颗粒体系由于表面等离子体效应,在太赫兹（THz）电磁波段出现的异常透射现象.通过THz时域光谱实验测量,发现THz波的透射强度不仅随着金属颗粒体系的厚度减小,而且当颗粒体系的横向尺寸大于THz光斑时,透射强度会随着体系横向尺寸的增大而减小,并伴随着透射时间的延迟.同时发现,入射THz电磁场在导电粒子体系中激发的表面等离子波主要沿着体系的边界传播. 关键词： 太赫兹电磁波 金属颗粒 表面等离子体     

Global regularity of the 4D restricted Euler equations

We are concerned with the critical threshold phenomena in the restricted Euler (RE) equations. Using the spectral and trace dynamics we identify the critical thresholds for the 3D and 4D restricted Euler equations. It is well known that the 3D RE solutions blow up. Projected on the 3-sphere, the set of initial eigenvalues which give rise to bounded stable solutions is reduced to a single point, which confirms that the 3D RE blowup is generic. In contrast, we identify a surprisingly rich set of the initial spectrum on the 4-sphere which yields global smooth solutions; thus, 4D regularity is generic.     

Complete Equivalence of the Gibbs Ensembles for One-Dimensional Markov Systems

We show the equivalence of the Gibbs ensembles at the level of measures for one-dimensional Markov-Systems with arbitrary boundary conditions. That is, the limit of the microcanonical Gibbs ensemble is a Gibbs measure with an interaction depending on the microcanonical constraint. In fact the usual microcanonical condition is replaced by the sharper constraint that all type frequencies of neighboring spins (including the boundary spins) are fixed. When conditioning on a set of different frequencies of neighboring spins compatible with physical quantities like energy density we get the usual microcanonical ensemble. We show that the limit is a Gibbs measure for a nearest neighbor potential depending on the pair measure which maximizes the entropy on the given set of pair measures. For this we show the large deviation property of the pair empirical measure for arbitrary boundary conditions. We establish analogous results for finite range potentials.     

The inhomogeneous Suslov problem

We consider the Suslov problem of nonholonomic rigid body motion with inhomogeneous constraints. We show that if the direction along which the Suslov constraint is enforced is perpendicular to a principal axis of inertia of the body, then the reduced equations are integrable and, in the generic case, possess a smooth invariant measure. Interestingly, in this generic case, the first integral that permits integration is transcendental and the density of the invariant measure depends on the angular velocities. We also study the Painlevé property of the solutions.     

Filling up complex spectral regions through non-Hermitian disordered chains

Eigenspectra that fill regions in the complex plane have been intriguing to many, inspiring research from random matrix theory to esoteric semi-infinite bounded non-Hermitian lattices. In this work, we propose a simple and robust ansatz for constructing models whose eigenspectra fill up generic prescribed regions. Our approach utilizes specially designed non-Hermitian random couplings that allow the co-existence of eigenstates with a continuum of localization lengths, mathematically emulating the effects of semi-infinite boundaries. While some of these couplings are necessarily long-ranged, they are still far more local than what is possible with known random matrix ensembles. Our ansatz can be feasibly implemented in physical platforms such as classical and quantum circuits, and harbors very high tolerance to imperfections due to its stochastic nature.     

Spin freezing in geometrically frustrated antiferromagnets with weak disorder

We investigate the consequences for geometrically frustrated antiferromagnets of weak disorder in the strength of exchange interactions. Taking as a model the classical Heisenberg antiferromagnet with nearest neighbor exchange on the pyrochlore lattice, we examine low-temperature behavior. We show that spatial modulation of exchange generates long-range effective interactions within the extensively degenerate ground states of the clean system. Using Monte Carlo simulations, we find a spin glass transition at a temperature set by the disorder strength. Disorder of this type, which is generated by random strains in the presence of magnetoelastic coupling, may account for the spin freezing observed in many geometrically frustrated magnets.     

Minimum weight design of beams in torsional vibration with several frequency constraints

The design of beams of cantilever form carrying and end inertia so as to minimize the total mass subject to the constraint that one, two or three of its torsional natural frequencies are fixed at specified values is considered. The problem is stated in variational form with the constraints introduced through Lagrange multipliers. The problem is taken analytically as far as possible and reduces to a set of first order non-linear differential equations. These are integrated numerically. The known solutions for less constrained problems are used as a basis from which to iterate to the required solutions. Optimum profiles and tables of numerical data computed for various examples are given.     

Models of fragmentation with composite power laws

Some models for binary fragmentation are introduced in which a time dependent transition size produces two regions of fragment sizes above and below the transition size. In the first model we assume a fixed rate of fragmentation for the largest fragment and two different rates of fragmentation in the two regions of sizes above and below the transition size. The model is solved exactly in the long time limit to reveal stable time-invariant solutions for the fragment size and mass distributions. These solutions exhibit composite power law behaviours; power laws with two different exponents for fragments in smaller and larger regions. A special case of the model with no fragmentation in the smaller size region is also examined. Another model is also introduced which have three regions of fragment sizes with different rates of fragmentation. The similarities between the stable distributions in our models and composite power law distributions from experimental work on shock fragmentation of long thin glass rods and thick clay plates are discussed.     

Flat Currents and Solutions of Sigma Model on Supercoset Targets with Z2m Grading

We find one parameter fiat currents of the sigma model on supercoset targets with Z2m grading given by Young satisfaction equations of motion and the Virasoro constraint. This means that one can generate a series of classical solutions from the original one. For these new solutions one can also construct fiat currents and conserved charges, which form the same set with the original one.