Search

Multi-layer neural networks are among the most powerful models in machine learning, yet the fundamental reasons for this success defy mathematical understanding. Learning a neural network requires to optimize a non-convex high-dimensional objective (risk function), a problem which is usually attacked using stochastic gradient descent (SGD). Does SGD converge to a global optimum of the risk or only to a local optimum? In the first case, does this happen because local minima are absent, or because SGD somehow avoids them? In the second, why do local minima reached by SGD have good generalization properties? In this paper we consider a simple case, namely two-layers neural networks, and prove that -in a suitable scaling limit- SGD dynamics is captured by a certain non-linear partial differential equation (PDE) that we call distributional dynamics (DD). We then consider several specific examples, and show how DD can be used to prove convergence of SGD to networks with nearly ideal generalization error. This description allows to 'average-out' some of the complexities of the landscape of neural networks, and can be used to prove a general convergence result for noisy SGD., Comment: 103 pages

Let ${\boldsymbol A}\in{\mathbb R}^{n\times n}$ be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing $\langle{\boldsymbol \sigma},{\boldsymbol A}{\boldsymbol \sigma}\rangle$ over binary vectors ${\boldsymbol \sigma}\in\{+1,-1\}^n$. In the language of statistical physics, this amounts to finding the ground state of the Sherrington-Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any $\varepsilon>0$, outputs ${\boldsymbol \sigma}_*\in\{-1,+1\}^n$ such that $\langle{\boldsymbol \sigma}_*,{\boldsymbol A}{\boldsymbol \sigma}_*\rangle$ is at least $(1-\varepsilon)$ of the optimum value, with probability converging to one as $n\to\infty$. The algorithm's time complexity is $C(\varepsilon)\, n^2$. It is a message-passing algorithm, but the specific structure of its update rules is new. As a side result, we prove that, at (low) non-zero temperature, the algorithm constructs approximate solutions of the Thouless-Anderson-Palmer equations., Comment: 27 pages

We consider the Sherrington–Kirkpatrick model of spin glasses with ferromagnetically biased couplings. For a specific choice of the couplings mean, the resulting Gibbs measure is equivalent to the Bayesian posterior for a high-dimensional estimation problem known as “${\mathbb{Z}}_{2}$ synchronization.” Statistical physics suggests to compute the expectation with respect to this Gibbs measure (the posterior mean in the synchronization problem), by minimizing the so-called Thouless–Anderson–Palmer (TAP) free energy, instead of the mean field (MF) free energy. We prove that this identification is correct, provided the ferromagnetic bias is larger than a constant (i.e., the noise level is small enough in synchronization). Namely, we prove that the scaled $\ell _{2}$ distance between any low energy local minimizers of the TAP free energy and the mean of the Gibbs measure vanishes in the large size limit. Our proof technique is based on upper bounding the expected number of critical points of the TAP free energy using the Kac–Rice formula.

We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by Krzakala et al. \cite{KrzakalaEtAl}, message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of non-zero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate $\delta$ exceeds the (upper) R\'enyi information dimension of the signal, $\uRenyi(p_X)$. More precisely, for a sequence of signals of diverging dimension $n$ whose empirical distribution converges to $p_X$, reconstruction is with high probability successful from $\uRenyi(p_X)\, n+o(n)$ measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension $n$ and $k(n)$ non-zero entries, this implies reconstruction from $k(n)+o(n)$ measurements. For `discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from $o(n)$ measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal $p_X$., Comment: 60 pages, 7 figures, Sections 3,5 and Appendices A,B are added. The stability constant is quantified (cf Theorem 1.7)

Let $Z(F)$ be the number of solutions of a random $k$-satisfiability formula $F$ with $n$ variables and clause density $\alpha$. Assume that the probability that $F$ is unsatisfiable is $O(1/\log(n)^{1+\e})$ for $\e>0$. We show that (possibly excluding a countable set of `exceptional' $\alpha$'s) the number of solutions concentrate in the logarithmic scale, i.e., there exists a non-random function $\phi(\alpha)$ such that, for any $\delta>0$, $(1/n)\log Z(F)\in [\phi-\delta,\phi+\delta]$ with high probability. In particular, the assumption holds for all $\alpha

Statistical inference problems arising within signal processing, data mining, and machine learning naturally give rise to hard combinatorial optimization problems. These problems become intractable when the dimensionality of the data is large, as is often the case for modern datasets. A popular idea is to construct convex relaxations of these combinatorial problems, which can be solved efficiently for large scale datasets. Semidefinite programming (SDP) relaxations are among the most powerful methods in this family, and are surprisingly well-suited for a broad range of problems where data take the form of matrices or graphs. It has been observed several times that, when the `statistical noise' is small enough, SDP relaxations correctly detect the underlying combinatorial structures. In this paper we develop asymptotic predictions for several `detection thresholds,' as well as for the estimation error above these thresholds. We study some classical SDP relaxations for statistical problems motivated by graph synchronization and community detection in networks. We map these optimization problems to statistical mechanics models with vector spins, and use non-rigorous techniques from statistical mechanics to characterize the corresponding phase transitions. Our results clarify the effectiveness of SDP relaxations in solving high-dimensional statistical problems., Comment: 71 pages, 24 pdf figures

We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subset of vertices. This can be regarded as a model for the problem of finding a tightly knitted community in a social network, or a cluster in a relational dataset. In this paper we present two sets of contributions: $(i)$ We use the cavity method from spin glass theory to derive an exact phase diagram for the reconstruction problem. In particular, as the difference in edge probability increases, the problem undergoes two phase transitions, a static phase transition and a dynamic one. $(ii)$ We establish rigorous bounds on the dynamic phase transition and prove that, above a certain threshold, a local algorithm (belief propagation) correctly identify most of the hidden set. Below the same threshold \emph{no local algorithm} can achieve this goal. However, in this regime the subset can be identified by exhaustive search. For small hidden sets and large average degree, the phase transition for local algorithms takes an intriguingly simple form. Local algorithms succeed with high probability for ${\rm deg}_{\rm in} - {\rm deg}_{\rm out} > \sqrt{{\rm deg}_{\rm out}/e}$ and fail for ${\rm deg}_{\rm in} - {\rm deg}_{\rm out} < \sqrt{{\rm deg}_{\rm out}/e}$ (with ${\rm deg}_{\rm in}$, ${\rm deg}_{\rm out}$ the average degrees inside and outside the community). We argue that spectral algorithms are also ineffective in the latter regime. It is an open problem whether any polynomial time algorithms might succeed for ${\rm deg}_{\rm in} - {\rm deg}_{\rm out} < \sqrt{{\rm deg}_{\rm out}/e}$., 30 pages, 8 pdf figures

Gallager codes are the best error-correcting codes to-date. In this paper we study them by using the tools of statistical mechanics. The corresponding statistical mechanics model is a spin model on a sparse random graph. The model can be solved by elementary methods (i.e. without replicas) in a large connectivity limit. For low enough temperatures it presents a completely frozen glassy phase (q_{EA}=1). The same scenario is shown to hold for finite connectivities. In this case we adopt the replica approach and exhibit a one-step replica symmetry breaking order parameter. We argue that our ansatz yields the exact solution of the model. This allows us to determine the whole phase diagram and to understand the performances of Gallager codes., Comment: 27 pages, 8 eps figures

We study the two-dimensional renormalization-group flow induced by perturbations that reduce the global symmetry of the O(3) sigma-model to the discrete symmetries of Platonic solids. We estimate the value of the correlation length at which differences in the behaviour of the various models should be expected. For the icosahedron model, we find xi > 200. We provide an explanation for the recent numerical results of Patrascioiu and Seiler and of Hasenfratz and Niedermayer., 12 pages, revised version

The problem of detecting communities in a graph is maybe one the most studied inference problems, given its simplicity and widespread diffusion among several disciplines. A very common benchmark for this problem is the stochastic block model or planted partition problem, where a phase transition takes place in the detection of the planted partition by changing the signal-to-noise ratio. Optimal algorithms for the detection exist which are based on spectral methods, but we show these are extremely sensible to slight modification in the generative model. Recently Javanmard, Montanari and Ricci-Tersenghi (arXiv:1511.08769) have used statistical physics arguments, and numerical simulations to show that finding communities in the stochastic block model via semidefinite programming is quasi optimal. Further, the resulting semidefinite relaxation can be solved efficiently, and is very robust with respect to changes in the generative model. In this paper we study in detail several practical aspects of this new algorithm based on semidefinite programming for the detection of the planted partition. The algorithm turns out to be very fast, allowing the solution of problems with $O(10^5)$ variables in few second on a laptop computer., Comment: 12 pages, 7 figures. Proceedings for the HD3-2015 conference (Kyoto, Dec 14-17, 2015)

The XOR-satisfiability (XORSAT) problem requires finding an assignment of $n$ Boolean variables that satisfy $m$ exclusive OR (XOR) clauses, whereby each clause constrains a subset of the variables. We consider random XORSAT instances, drawn uniformly at random from the ensemble of formulae containing $n$ variables and $m$ clauses of size $k$. This model presents several structural similarities to other ensembles of constraint satisfaction problems, such as $k$-satisfiability ($k$-SAT), hypergraph bicoloring and graph coloring. For many of these ensembles, as the number of constraints per variable grows, the set of solutions shatters into an exponential number of well-separated components. This phenomenon appears to be related to the difficulty of solving random instances of such problems. We prove a complete characterization of this clustering phase transition for random $k$-XORSAT. In particular, we prove that the clustering threshold is sharp and determine its exact location. We prove that the set of solutions has large conductance below this threshold and that each of the clusters has large conductance above the same threshold. Our proof constructs a very sparse basis for the set of solutions (or the subset within a cluster). This construction is intimately tied to the construction of specific subgraphs of the hypergraph associated with an instance of $k$-XORSAT. In order to study such subgraphs, we establish novel local weak convergence results for them., Published at http://dx.doi.org/10.1214/14-AAP1060 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We consider ferromagnetic Ising models on graphs that converge locally to trees. Examples include random regular graphs with bounded degree and uniformly random graphs with bounded average degree. We prove that the "cavity" prediction for the limiting free energy per spin is correct for any positive temperature and external field. Further, local marginals can be approximated by iterating a set of mean field (cavity) equations. Both results are achieved by proving the local convergence of the Boltzmann distribution on the original graph to the Boltzmann distribution on the appropriate infinite random tree., Comment: Published in at http://dx.doi.org/10.1214/09-AAP627 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

A voter sits on each vertex of an infinite tree of degree $k$, and has to decide between two alternative opinions. At each time step, each voter switches to the opinion of the majority of her neighbors. We analyze this majority process when opinions are initialized to independent and identically distributed random variables. In particular, we bound the threshold value of the initial bias such that the process converges to consensus. In order to prove an upper bound, we characterize the process of a single node in the large $k$-limit. This approach is inspired by the theory of mean field spin-glass and can potentially be generalized to a wider class of models. We also derive a lower bound that is nontrivial for small, odd values of $k$., Published in at http://dx.doi.org/10.1214/10-AAP729 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We define a new family of random spin models with one-dimensional structure, finite-range multi-spin interactions, and bounded average degree (number of interactions in which each spin participates). Unfrustrated ground states can be described as solutions of a sparse, band diagonal linear system, thus allowing for efficient numerical analysis. In the limit of infinite interaction range, we recover the so-called XORSAT (diluted p-spin) model, that is known to undergo a random first order phase transition as the average degree is increased. Here we investigate the most important consequences of a large but finite interaction range: (i) Fluctuation-induced corrections to thermodynamic quantities; (ii) The need of an inhomogeneous (position dependent) order parameter; (iii) The emergence of a finite mosaic length scale. In particular, we study the correlation length divergence at the (mean-field) glass transition., Comment: 25 pages, 9 eps figures

We consider a disordered spin model with multi-spin interactions undergoing a glass transition. We introduce a dynamic and a static length scales and compute them in the Kac limit (long--but--finite range interactions). They diverge at the dynamic and static phase transition with exponents (respectively) -1/4 and -1. The two length scales are approximately equal well above the mode coupling transition. Their discrepancy increases rapidly as this transition is approached. We argue that this signals a crossover from mode coupling to activated dynamics., Comment: 4 pages, 4 eps figures. New version conform to the published one

An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space (the set of assignments). We consider two prototypical problem ensembles (random k-satisfiability and q-coloring of random regular graphs), and study the uniform measure with support on S. As the number of constraints per variable increases, this measure first decomposes into an exponential number of pure states ("clusters"), and subsequently condensates over the largest such states. Above the condensation point, the mass carried by the n largest states follows a Poisson-Dirichlet process. For typical large instances, the two transitions are sharp. We determine for the first time their precise location. Further, we provide a formal definition of each phase transition in terms of different notions of correlation between distinct variables in the problem. The degree of correlation naturally affects the performances of many search/sampling algorithms. Empirical evidence suggests that local Monte Carlo Markov Chain strategies are effective up to the clustering phase transition, and belief propagation up to the condensation point. Finally, refined message passing techniques (such as survey propagation) may beat also this threshold., Comment: 6 pages, 6 figures, slightly revised version

Consider an information source generating a symbol at the root of a tree network whose links correspond to noisy communication channels, and broadcasting it through the network. We study the problem of reconstructing the transmitted symbol from the information received at the leaves. In the large system limit, reconstruction is possible when the channel noise is smaller than a threshold. We show that this threshold coincides with the dynamical (replica symmetry breaking) glass transition for an associated statistical physics problem. Motivated by this correspondence, we derive a variational principle which implies new rigorous bounds on the reconstruction threshold. Finally, we apply a standard numerical procedure used in statistical physics, to predict the reconstruction thresholds in various channels. In particular, we prove a bound on the reconstruction problem for the antiferromagnetic ``Potts'' channels, which implies, in the noiseless limit, new results on random proper colorings of infinite regular trees. This relation to the reconstruction problem also offers interesting perspective for putting on a clean mathematical basis the theory of glasses on random graphs., 34 pages, 16 eps figures

The Glauber dynamics of disordered spin models with multi-spin interactions on sparse random graphs (Bethe lattices) is investigated. Such models undergo a dynamical glass transition upon decreasing the temperature or increasing the degree of constrainedness. Our analysis is based upon a detailed study of large scale rearrangements which control the slow dynamics of the system close to the dynamical transition. Particular attention is devoted to the neighborhood of a zero temperature tricritical point. Both the approach and several key results are conjectured to be valid in a considerably more general context., 56 pages, 38 eps figures

Glassy systems are characterized by an extremely sluggish dynamics without any simple sign of long range order. It is a debated question whether a correct description of such phenomenon requires the emergence of a large correlation length. We prove rigorous bounds between length and time scales implying the growth of a properly defined length when the relaxation time increases. Our results are valid in a rather general setting, which covers finite-dimensional and mean field systems. As an illustration, we discuss the Glauber (heat bath) dynamics of p-spin glass models on random regular graphs. We present the first proof that a model of this type undergoes a purely dynamical phase transition not accompanied by any thermodynamic singularity., Comment: 24 pages, 3 figures; published version

We introduce a method for computing corrections to Bethe approximation for spin models on arbitrary lattices. Unlike cluster variational methods, the new approach takes into account fluctuations on all length scales. The derivation of the leading correction is explained and applied to two simple examples: the ferromagnetic Ising model on d-dimensional lattices, and the spin glass on random graphs (both in their high-temperature phases). In the first case we rederive the well-known Ginzburg criterion and the upper critical dimension. In the second, we compute finite-size corrections to the free energy., 16 pages, 2 eps figures

A new method for analyzing low density parity check (LDPC) codes and low density generator matrix (LDGM) codes under bit maximum a posteriori probability (MAP) decoding is introduced. The method is based on a rigorous approach to spin glasses developed by Francesco Guerra. It allows to construct lower bounds on the entropy of the transmitted message conditional to the received one. Based on heuristic statistical mechanics calculations, we conjecture such bounds to be tight. The result holds for standard irregular ensembles when used over binary input output symmetric channels. The method is first developed for Tanner graph ensembles with Poisson left degree distribution. It is then generalized to `multi-Poisson' graphs, and, by a completion procedure, to arbitrary degree distribution., 28 pages, 9 eps figures; Second version contains a generalization of the previous result

In this paper we investigate the behavior of iteratively decoded low-density parity-check codes over the binary erasure channel in the so-called ``waterfall region." We show that the performance curves in this region follow a very basic scaling law. We conjecture that essentially the same scaling behavior applies in a much more general setting and we provide some empirical evidence to support this conjecture. The scaling law, together with the error floor expressions developed previously, can be used for fast finite-length optimization., Comment: 45 pages, 14 figures

We develop a new analytic approach for the study of lattice heteropolymers, and apply it to copolymers with correlated Markovian sequences. According to our analysis, heteropolymers present three different dense phases depending upon the temperature, the nature of the monomer interactions, and the sequence correlations: (i) a liquid phase, (ii) a ``soft glass'' phase, and (iii) a ``frozen glass'' phase. The presence of the new intermediate ``soft glass'' phase is predicted for instance in the case of polyampholytes with sequences that favor the alternation of monomers. Our approach is based on the cavity method, a refined Bethe Peierls approximation adapted to frustrated systems. It amounts to a mean field treatment in which the nearest neighbor correlations, which are crucial in the dense phases of heteropolymers, are handled exactly. This approach is powerful and versatile, it can be improved systematically and generalized to other polymeric systems.

The low temperature phase of discontinuous mean-field spin glasses is characterized by the appearance of an exponential number of metastable states. Which ones among these states dominate the out-of-equilibrium dynamics of these systems? In order to answer this question, we compare high-precision numerical simulations of a diluted $p$-spin model with a cavity computation of the threshold energy. Our main conclusion is that the aging dynamics is dominated by different layers of metastable states depending on the cooling schedule. In order to perform our analysis, we present a method for computing the marginality condition of diluted spin glasses at non-zero temperature., Comment: 19 pages, 6 eps figures

We reconsider the one-step replica-symmetry-breaking (1RSB) solutions of two random combinatorial problems: k-XORSAT and k-SAT. We present a general method for establishing the stability of these solutions with respect to further steps of replica-symmetry breaking. Our approach extends the ideas of [A.Montanari and F. Ricci-Tersenghi, Eur.Phys.J. B 33, 339 (2003)] to more general combinatorial problems. It turns out that 1RSB is always unstable at sufficiently small clauses density alpha or high energy. In particular, the recent 1RSB solution to 3-SAT is unstable at zero energy for alpha< alpha_m, with alpha_m\approx 4.153. On the other hand, the SAT-UNSAT phase transition seems to be correctly described within 1RSB., 26 pages, 7 eps figures

In this article we discuss several aspects of the stochastic dynamics of spin models. The paper has two independent parts. Firstly, we explore a few properties of the multi-point correlations and responses of generic systems evolving in equilibrium with a thermal bath. We propose a fluctuation principle that allows us to derive fluctuation-dissipation relations for many-time correlations and linear responses. We also speculate on how these features will be modified in systems evolving slowly out of equilibrium, as finite-dimensional or dilute spin-glasses. Secondly, we present a formalism that allows one to derive a series of approximated equations that determine the dynamics of disordered spin models on random (hyper) graphs., 25 pages

The low-temperature phase of discontinuous mean-field spin glasses is generally described by a one-step replica symmetry breaking (1RSB) Ansatz. The Gardner transition, i.e. a very-low-temperature phase transition to a full replica symmetry breaking (FRSB) phase, is often regarded as an inessential, and somehow exotic phenomenon. In this paper we show that the metastable states which are relevant for the out-of-equilibrium dynamics of such systems are always in a FRSB phase. The only exceptions are (to the best of our knowledge) the p-spin spherical model and the random energy model (REM). We also discuss the consequences of our results for aging dynamics and for local search algorithms in hard combinatorial problems., 14 pages, 7 figures

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., Comment: 4 pages, 3 figures; published version

We consider the dynamics of a diluted mean-field spin glass model in the aging regime. The model presents a particularly rich heterogeneous behavior. In order to catch this behavior, we perform a **spin-by-spin analysis** for a **given disorder realization**. The results compare well with the outcome of a static calculation which uses the ``survey propagation'' algorithm of Mezard, Parisi, and Zecchina [Sciencexpress 10.1126/science.1073287 (2002)]. We thus confirm the connection between statics and dynamics at the level of single degrees of freedom. Moreover, working with single-site quantities, we can introduce a new response-vs-correlation plot, which clearly shows how heterogeneous degrees of freedom undergo coherent structural rearrangements. Finally we discuss the general scenario which emerges from our work and (possibly) applies to more realistic glassy models. Interestingly enough, some features of this scenario can be understood recurring to thermometric considerations., 4 pages, 5 figures (7 eps files)

The state-of-the-art error correcting codes are based on large random constructions (random graphs, random permutations, ...) and are decoded by linear-time iterative algorithms. Because of these features, they are remarkable examples of diluted mean-field spin glasses, both from the static and from the dynamic points of view. We analyze the behavior of decoding algorithms using the mapping onto statistical-physics models. This allows to understand the intrinsic (i.e. algorithm independent) features of this behavior., Comment: 40 pages, 29 eps figures

We consider a two-dimensional sigma-model with discrete icosahedral/dodecahedral symmetry. We present high-precision finite-size numerical results that show that the continuum limit of this model is different from the continuum limit of the rotationally invariant O(3) sigma-model., Lattice2001(spin), 3 pages, 4 figures

We consider a two-dimensional $\sigma$-model with discrete icosahedral/dodecahedral symmetry. Using the perturbative renormalization group, we argue that this model has a different continuum limit with respect to the O(3) $\sigma$ model. Such an argument is confirmed by a high-precision numerical simulation., Comment: 5 pages including 6 postscript figures. Talk given at HEP01 in Budapest, Hungary, in July 2001

Turbo codes are a very efficient method for communicating reliably through a noisy channel. There is no theoretical understanding of their effectiveness. In [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., Comment: 26 pages, 3 eps figures

We consider the short-distance behaviour of the product of the Noether O(N) currents in the lattice nonlinear sigma-model. We compare the numerical results with the predictions of the operator product expansion, using one-loop perturbative renormalization-group improved Wilson coefficients. We find that, even on quite small lattices (m a \approx 1/6), the perturbative operator product expansion describes that data with an error of 5-10% in a large window 2a \ltapprox x \ltapprox m^{-1}. We present a detailed discussion of the possible systematic errors., 53 pages, 11 figures (26 eps files)

The operator product expansion is used to compute the matrix elements of composite renormalized operators on the lattice. We study the product of two fundamental fields in the two-dimensional sigma-model and discuss the possible sources of systematic errors. The key problem turns out to be the violation of asymptotic scaling., Lattice 99 (Improvement and Renormalization), 3 pages, 3 eps figures

The "turbo codes", recently proposed by Berrou et. al. are written as a disordered spin Hamiltonian. It is shown that there is a threshold Theta such that for signal to noise ratios v^2 / w^2 > Theta, the error probability per bit vanishes in the thermodynamic limit, i.e. the limit of infinitly 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., 23 pages, 6 figures: Fig.2 has been replaced (in the preceding version it was identical to Fig.1)

It has been recently proposed to use the operator product expansion to evaluate the expectation values of renormalized operators without the need of a direct computation of the relevant renormalization constants. We test the viability of this idea in the two-dimensional non-linear sigma-model discussing the non-perturbative renormalization of the energy-momentum tensor., Comment: LATTICE98(matrixelement), uses espcrc2 and epsfig, 3 pages, 2 eps figures

For the O(N) sigma-model we studied the improvement program for actions with two- and four-spin interactions. An interesting example is an action which is reflection-positive, on-shell improved, and has all the coupling defined on an elementary plaquette. We show the large N solution and preliminary Monte Carlo results for N=3., Comment: Talk presented at Lattice '97 (Improvement and Renormalisation), Edinburgh (UK), July 1997. LaTeX2e, 3 pages, 2 figures, uses espcrc2 and epsfig

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., Comment: 30 pages, 14 figures, typos corrected, discussion of appendix C expanded with a new figure

We study the finite-size behaviour of a tree-level on-shell improved action for the N-vector model. We present numerical results for N=3 and analytic results in the large-N limit for the mass gap. We also report a perturbative computation at one loop of the mass gap for states of spatial momentum p. We present a detailed comparison of the behaviour of this action with that of other formulations, including the perfect action, and a critical discussion of the different approaches to the problem of action improvement., LaTex2e, 34 pages, 5 ps figures, uses epsf, epsfig, amsfont, cite.sty

We investigate numerically the dynamics of three different spin models in the aging regime. Each of these models is meant to be representative of a distinct class of aging behavior: coarsening systems, discontinuous spin glasses, and continuous spin glasses. In order to study dynamic heterogeneities induced by quenched disorder, we consider single-spin observables for a given disorder realization. In some simple cases we are able to provide analytical predictions for single-spin response and correlation functions. The results strongly depend upon the model considered. It turns out that, by comparing the slow evolution of a few different degrees of freedom, one can distinguish between different dynamic classes. As a conclusion we present the general properties which can be induced from our results, and discuss their relation with thermometric arguments., 39 pages, 36 figures