Statistical physics of loopy interactions: independent-loop approximation and beyond

We consider an interacting system of spin variables on a loopy interaction graph, identified by a tree graph and a set of loopy interactions. We start from a high-temperature expansion for loopy interactions represented by a sum of non-negative contributions from all the possible frustration-free loop configurations. We then compute the loop corrections using different approximations for the nonlocal loop interactions induced by the spin correlations in the tree graph. For distant loopy interactions, we can exploit the exponential decay of correlations in the tree interaction graph to compute loop corrections within an independent-loop approximation. Higher orders of the approximation are obtained by considering the correlations between the nearby loopy interactions involving larger number of spin variables. In particular, the sum over the loop configurations can be computed "exactly" by the belief propagation algorithm in the low orders of the approximation as long as the loopy interactions have a tree structure. These results might be useful in developing more accurate and convergent message-passing algorithms exploiting the structure of loopy interactions.

Patterned and disordered continuous Abelian sandpile model

We study critical properties of the continuous Abelian sandpile model with anisotropies in toppling rules that produce ordered patterns on it. Also, we consider the continuous directed sandpile model perturbed by a weak quenched randomness, study critical behavior of the model using perturbative conformal field theory, and show that the model has a random fixed point.

Direct evidence for conformal invariance of avalanche frontiers in sandpile models

Appreciation of stochastic Loewner evolution (SLE_{kappa}) , as a powerful tool to check for conformal invariant properties of geometrical features of critical systems has been rising. In this paper we use this method to check conformal invariance in sandpile models. Avalanche frontiers in Abelian sandpile model are numerically shown to be conformally invariant and can be described by SLE with diffusivity kappa=2 . This value is the same as value obtained for loop-erased random walks. The fractal dimension and Schramm's formula for left passage probability also suggest the same result. We also check the same properties for Zhang's sandpile model.

Simplifying random satisfiability problems by removing frustrating interactions

How can we remove some interactions (generate shorter clauses) in a constraint satisfaction problem (CSP) such that it still remains satisfiable? In this paper we study a modified survey propagation algorithm that enables us to address this question for a prototypical CSP, i.e., random K-satisfiability problem. The average number of removed interactions is controlled by a tuning parameter in the algorithm. If the original problem is satisfiable then we are able to construct satisfiable subproblems ranging from the original one to a minimal one with minimum possible number of interactions. The minimal satisfiable subproblems will directly provide the solutions of the original problem.

Biased random satisfiability problems: from easy to hard instances

In this paper we study biased random K -satisfiability ( K -SAT) problems in which each logical variable is negated with probability p . This generalization provides us a crossover from easy to hard problems and would help us in a better understanding of the typical complexity of random K -SAT problems. The exact solution of 1-SAT case is given. The critical point of K -SAT problems and results of replica method are derived in the replica symmetry framework. It is found that in this approximation alpha(c) proportional p(-(K-1)) for p --> 0. Solving numerically the survey propagation equations for K = 3 we find that for p < p* approximately 0.17 there is no replica symmetry breaking and still the SAT-UNSAT transition is discontinuous.