Turbo codes: the phase transition

Turbo codes are a very efficient method for communicating reliably through a noisy channel. There is no theoretical understanding of their effectiveness. In reference [1] they are mapped onto a class of disordered spin models. The analytical calculations concerning these models are reported here. We prove the existence of a no-error phase and compute its local stability threshold. As a byproduct, we gain some insight into the dynamics of the decoding algorithm. Received 14 March 2000     

The statistical mechanics of turbo codes

The “turbo codes”, recently proposed by Berrou et al. [1] are written as a disordered spin Hamiltonian. It is shown that there exists a threshold such that for signal to noise ratios the error probability per bit vanishes in the thermodynamic limit, i.e. the limit of infinitely long sequences. The value of the threshold has been computed for two particular turbo codes. It is found that it depends on the code. These results are compared with numerical simulations. Received 14 March 2000 and Received in final form 17 July 2000     

The kinetic spin-1 Blume-Capel model with competing dynamics

We have studied by means of Monte-Carlo simulation and exact finite-size analysis, the spin-1 Blume Capel model with Glauber and Kawasaki dynamics. The Kawasaki spin-exchange process transfers energy into the system from an external source. Some phase diagrams of the model are presented. For some parameter values, the system displays a kind of self-organization phenomenon within the disordered phase. Received 15 February 2000     

The Bethe lattice spin glass revisited

So far the problem of a spin glass on a Bethe lattice has been solved only at the replica symmetric level, which is wrong in the spin glass phase. Because of some technical difficulties, attempts at deriving a replica symmetry breaking solution have been confined to some perturbative regimes, high connectivity lattices or temperature close to the critical temperature. Using the cavity method, we propose a general non perturbative solution of the Bethe lattice spin glass problem at a level of approximation which is equivalent to a one step replica symmetry breaking solution. The results compare well with numerical simulations. The method can be used for many finite connectivity problems appearing in combinatorial optimization. Received 27 September 2000     

Aging dynamics of Edwards-Anderson spin glasses

We analyze by means of extensive computer simulations the out of equilibrium dynamics of Edwards-Anderson spin glasses in d = 4 and d = 6 dimensions with ± J interactions. In particular, we focus our analysis on the scaling properties of the two-time autocorrelation function in a wide range of temperatures from T = 0.07 T _c to T = 0.75 T _c in both systems. In both the 4 d and 6 d models at very low temperatures we study the effects of discretization of energy levels. Strong sub-aging behaviors are found. We argue that this is because in the times accessible to our simulations the systems are only able to probe activated dynamics through the lowest discrete energy levels and remain trapped around nearly flat regions of the energy landscape. For temperatures T ≥ 0.5 T _c in 4 d and 6 d we find logarithmic scalings that are compatible with simple dynamical ultrametricity. Nevertheless the behaviour of the systems, even in 6 d is very different from the mean field SK model results. Received 21 October 2002 / Received in final form 13 January 2003 Published online 11 April 2003 RID="a" ID="a"Associate researcher of the Abdus Salam International Centre for Theoretical Physics; e-mail: stariolo@if.ufrgs.br; http://www.if.ufrgs.br/stariolo RID="b" ID="b"Present address: The Abdus Salam International Centre for Theoretical Physics, Strada Costiera 11, 34014 Trieste, Italy e-mail: mmontemu@ictp.trieste.it RID="c" ID="c"e-mail: tamarit@famaf.unc.edu.ar     

Dynamic spin-glass behavior in a disorder-free,two-component model of quantum frustrated magnets

Motivated by the observation of a spin-glass transition in almost disorder-free Kagome antiferromagnets, and by the specific form of the effective low-energy model of the S = 1/2, trimerized Kagome antiferromagnet, we investigate the possibility to obtain a spin-glass behavior in two-component, disorder-free models. We concentrate on a toy-model, a modified Ashkin-Teller model in a magnetic field that couples only to one species of spins, for which we prove that a dynamic spin-glass behavior occurs. The dynamics of the magnetization is closely related to that of the underlying Ising model in zero field in which spins and pseudo-spins are intimately coupled. The spin-glass like history dependence of the magnetization is a consequence of the ageing of the underlying Ising model. Received 21 September 2001 and Received in final form 16 January 2002     

The <Emphasis Type="Bold">±</Emphasis><Emphasis Type="Bold">J</Emphasis> spin glass in Migdal-Kadanoff approximation

We study the low-temperature phase of the three-dimensional ± J Ising spin glass in Migdal-Kadanoff approximation. At zero temperature, T = 0, the properties of the spin glass result from the ground-state degeneracy and can be elucidated using scaling arguments based on entropy. The approach to the asymptotic scaling regime is very slow, and the correct exponents are only visible beyond system sizes around 64. At T > 0, a crossover from the zero-temperature behaviour to the behaviour expected from the droplet picture occurs at length scales proportional to T ^-2/ds where d_s is the fractal dimension of a domain wall. Canonical droplet behaviour is not visible at any temperature for systems whose linear dimension is smaller than 16 lattice spacings, because the data are either affected by the zero-temperature behaviour or the critical point behaviour. Received 18 February 2001     

Ultrametricity between states at different temperatures in spin-glasses

We prove the existence of correlations between the equilibrium states at different temperatures of the multi-p-spin spherical spin-glass models with continuous replica symmetry breaking: there is no chaos in temperature in these models. Furthermore, the overlaps satisfy ultrametric relations. As a consequence the Parisi tree is essentially the same at all temperatures with lower branches developing when lowering the temperature. We conjecture that the reference free energies of the clusters are also fixed at all temperatures as in the generalized random-energy model. Received 18 March 2002 / Received in final form 14 June 2002 Published online 1st October 2002 RID="a" ID="a"e-mail: tommaso.rizzo@inwind.it     

On the finite size corrections to some random matching problems

We get back to the computation of the leading finite size corrections to some random link matching problems, first adressed by Mézard and Parisi [J. Phys. France 48, 1451 (1987)]. In the so-called bipartite case, their result is in contradiction with subsequent works. We show that they made some mistakes, and correcting them, we get the expected result. In the non bipartite case, we agree with their result but push the analytical treatment further. Received 28 April 2002 Published online 14 October 2002 RID="a" ID="a"e-mail: giorgio.parisi@roma1.infn.it RID="b" ID="b"e-mail: matthieu.ratieville@roma1.infn.it     

Neighborhood preferences in random matching problems

We consider a class of random matching problems where the distance between two points has a probability law which, for a small distance l, goes like l^r. In the framework of the cavity method, in the limit of an infinite number of points, we derive equations for p_k, the probability for some given point to be matched to its kth nearest neighbor in the optimal configuration. These equations are solved in two limiting cases: r = 0 -- where we recover p _k = 1/2^k, as numerically conjectured by Houdayer et al. and recently rigorously proved by Aldous -- and r→ + ∞. For 0 < r < + ∞, we are not able to solve the equations analytically, but we compute the leading behavior of p_k for large k. Received 14 February 2001     

Solvable lattice gas models of random hetero-polymers at finite density: I. Statics

We introduce -dimensional lattice gas versions of three common models of random hetero-polymers, in which both the polymer density and the density of the polymer-solvent mixture are finite. These solvable models give valuable insight into the problems related to the (quenched) average over the randomness in statistical mechanical models of proteins, without having to deal with the hard geometrical constraints occurring in finite-dimensional models. Our exact solution, which is specific to the -dimensional case, is compared to the results obtained by a saddle-point analysis and by the grand ensemble approach, both of which can also be applied to models of finite dimension. We find, somewhat surprisingly, that the saddle-point analysis can lead to qualitatively incorrect results. Received 15 June 1999 and Received in final form 14 October 1999     

A microscopic mechanism for rejuvenation and memory effects in spin glasses

Aging in spin glasses (and in some other systems) reveals astonishing effects of `rejuvenation and memory' upon temperature changes. In this paper, we propose microscopic mechanisms (at the scale of spin-spin interactions) which can be at the origin of such phenomena. Firstly, we recall that, in a frustrated system, the effective average interaction between two spins may take different values (possibly with opposite signs) at different temperatures. We give simple examples of such situations, which we compute exactly. Such mechanisms can explain why new ordering processes (rejuvenation) seem to take place in spin glasses when the temperature is lowered. Secondly, we emphasize the fact that inhomogeneous interactions do naturally lead to a wide distribution of relaxation times for thermally activated flips. `Memory spots' spontaneously appear, in the sense that the flipping time of some spin clusters becomes extremely long when the temperature is decreased. Such memory spots are capable of keeping the memory of previous ordering at a higher temperature while new ordering processes occur at a lower temperature. After a qualitative discussion of these mechanisms, we show in the numerical simulation of a simplified example that this may indeed work. Our conclusion is that certain chaos-like phenomena may show up spontaneously in any frustrated and inhomogeneous magnetic system, without impeding the occurrence of memory effects. Received 5 February 2001 and Received in final form 27 April 2001     

Dynamic fracture model for acoustic emission

We consider the spin-glass phase of the Sherrington-Kirkpatrick model in the presence of a magnetic field. The series expansion of the Parisi function q(x) is computed at high orders in powers of τ = T _c - T and H. We find that none of the Parisi-Toulouse scaling hypotheses on the q(x) behavior strictly holds, although some of them are violated only at high orders. The series is resummed yielding results in the whole spin-glass phase which are compared with those from a numerical evaluation of the q(x). At the high order considered, the transition turns out to be third order on the Almeida-Thouless line, a result which is confirmed rigorously computing the expansion of the solution near the line at finite τ. The transition becomes smoother for infinitesimally small field while it is third order at strictly zero field. Received 3 March 2003 Published online 4 June 2003 RID="a" ID="a"e-mail: andrea.crisanti@phys.uniroma1.it RID="b" ID="b"e-mail: tommaso.rizzo@phys.uniroma1.it RID="c" ID="c"e-mail: temtam@helios.elte.hu     

Non-equilibrium dynamics of simple spherical spin models

We investigate the non-equilibrium dynamics of spherical spin models with two-spin interactions. For the exactly solvable models of the d-dimensional spherical ferromagnet and the spherical Sherrington-Kirkpatrick (SK) model the asymptotic dynamics has for large times and large waiting times the same formal structure. In the limit of large waiting times we find in both models an intermediate time scale, scaling as a power of the waiting time with an exponent smaller than one, and thus separating the time-translation-invariant short-time dynamics from the aging regime. It is this time scale on which the fluctuation-dissipation theorem is violated. Aging in these models is similar to that observed in spin glasses at the level of correlation functions, but different at the level of response functions, and thus different at the level of experimentally accessible quantities like thermoremanent magnetization. Received 22 April 1999     

Generic replica symmetric field-theory for short range Ising spin glasses

Symmetry considerations and a direct, Hubbard-Stratonovich type, derivation are used to construct a replica field-theory relevant to the study of the spin glass transition of short range models in a magnetic field. A mean-field treatment reveals that two different types of transitions exist, whenever the replica number n is kept larger than zero. The Sherrington-Kirkpatrick critical point in zero magnetic field between the paramagnet and replica magnet (a replica symmetric phase with a nonzero spin glass order parameter) separates from the de Almeida-Thouless line, along which replica symmetry breaking occurs. We argue that for studying the de Almeida-Thouless transition around the upper critical dimension d = 6, it is necessary to use the generic cubic model with all the three bare masses and eight cubic couplings. The critical role n may play is also emphasized. To make perturbative calculations feasible, a new representation of the cubic interaction is introduced. To illustrate the method, we compute the masses in one-loop order. Some technical details and a list of vertex rules are presented to help future renormalisation-group calculations. Received 9 October 2001     

Renormalization group approach to spin glass systems

A renormalization group transformation suitable for spin glass models and, more generally, for disordered models, is presented. The procedure is non-standard in both the nature of the additional interactions and the coarse graining transformation, that is performed on the overlap probability measure. Universality classes are thus naturally defined on a large set of models, going from and Gaussian spin glasses to Ising and fully frustrated models, and others. The proposed analysis is tested numerically on the Edwards-Anderson model in d = 4. Good estimates of the critical index ν and of T _c are obtained, and an RG flow diagram is sketched for the first time. Received 17 November 2000     

Vertex cover problem studied by cavity method: Analytics and population dynamics

We study the vertex cover problem on finite connectivity random graphs by zero-temperature cavity method. The minimum vertex cover corresponds to the ground state(s) of a proposed Ising spin model. When the connectivity c > e = 2.718282, there is no state for this system as the reweighting parameter y, which takes a similar role as the inverse temperature β in conventional statistical physics, approaches infinity; consequently the ground state energy is obtained at a finite value of y when the free energy function attains its maximum value. The minimum vertex cover size at given c is estimated using population dynamics and compared with known rigorous bounds and numerical results. The backbone size is also calculated. Received 11 November 2002 Published online 1st April 2003 RID="a" ID="a"e-mail: zhou@mpikg-golm.mpg.de     

Aging and non-linear glassy dynamics in a mean field model

The mean field approach of glassy dynamics successfully describes systems which are out-of-equilibrium in their low temperature phase. In some cases an aging behaviour is found, with no stationary regime ever reached. In the presence of dissipative forces however, the dynamics is indeed stationary, but still out-of-equilibrium, as inferred by a significant violation of the fluctuation dissipation theorem. The mean field dynamics of a particle in a random but short-range correlated environment, offers the opportunity of observing both the aging and driven stationary regimes. Using a geometrical approach previously introduced by the author, we study here the relation between these two situations, in the pure relaxational limit, i.e. the zero temperature case. In the stationary regime, the velocity (v)-force (F) characteristics is a power law v∼F ⁴, while the characteristic times scale like powers of v, in agreement with an early proposal by Horner. The cross-over between the aging, linear-response regime and the non-linear stationary regime is smooth, and we propose a parametrization of the correlation functions valid in both cases, by means of an “effective time”. We conclude that aging and non-linear response are dual manifestations of a single out-of-equilibrium state, which might be a generic situation. Received 7 May 2000 and Received in final form 22 August 2000     

Probability distribution of inherent states in models of granular media and glasses

The present paper develops a Statistical Mechanics approach to the inherent states of glassy systems and granular materials by following the original ideas proposed by Edwards for granular media. We consider three lattice models (a diluted spin glass, a system of hard spheres under gravity and a hard-spheres binary mixture under gravity) introduced to describe glassy and granular systems. They are evolved using a “tap dynamics” analogous to that of experiments on granular media. We show that the asymptotic states reached in such a dynamics are not dependent on the particular sample history and are characterized by a few thermodynamical parameters. We assume that under stationarity these systems are distributed in their inherent states satisfying the principle of maximum entropy. This leads to a generalized Gibbs distribution characterized by new “thermodynamical” parameters, called “configurational temperatures” (related to Edwards compactivity for granular materials). Finally, we show by Monte Carlo calculations that the average of macroscopic quantities over the tap dynamics and over such distribution indeed coincide. In particular, in the diluted spin glass and in the system of hard spheres under gravity, the asymptotic states reached by the system are found to be described by a single “configurational temperature”. Whereas in the hard-spheres binary mixture under gravity the asymptotic states reached by the system are found to be described by two thermodynamic parameters, coinciding with the two configurational temperatures which characterize the distribution among the inherent states when the principle of maximum entropy is satisfied under the constraint that the energies of the two species are independently fixed. Received 19 March 2002 and Received in final form 14 June 2002