REPLICA

In this article we review the framework for spontaneous replica symmetry breaking. Subsequently that is applied to the example of the statistical mechanical description of the storage properties of a McCulloch¯ Pitts neuron, i.e., simple perceptron. It is shown that in the neuron problem, the general formula that is at the core of all problems admitting Parisi's replica symmetry breaking ansatz with a one-component order parameter appears. The details of Parisi's method are reviewed extensively, with regard to the wide range of systems where the method may be applied. Parisi's partial differential equation and related differential equations are discussed, and the Green function technique is introduced for the calculation of replica averages, the key to determining the averages of physical quantities. The Green function of the Fokker¯Planck equation due to Sompolinsky turns out to play the role of the statistical mechanical Green function in the graph rules for replica correlators. The subsequently obtained graph rules involve only tree graphs, as appropriate for a mean-field-like model. The lowest order Ward¯Takahashi identity is recovered analytically and shown to lead to the Goldstone modes in continuous replica symmetry breaking phases. The need for a replica symmetry breaking theory in the storage problem of the neuron has arisen due to the thermodynamical instability of formerly given solutions. Variational forms for the neuron's free energy are derived in terms of the order parameter function x(q), for different prior distribution of synapses. Analytically in the high temperature limit and numerically in generic cases various phases are identified, among them is one similar to the Parisi phase in long-range interaction spin glasses. Extensive quantities like the error per pattern change slightly with respect to the known unstable solutions, but there is a significant difference in the distribution of non-extensive quantities like the synaptic overlaps and the pattern storage stability parameter. A simulation result is also reviewed and compared with the prediction of the theory.

We discuss replica symmetry breaking (RSB) in spin glasses. We update work in this area, from both the analytical and numerical points of view. We give particular attention to the difficulties stressed by Newman and Stein concerning the problem of constructing pure states in spin glass systems. We mainly discuss what happens in finite-dimensional, realistic spin glasses. Together with a detailed review of some of the most important features, facts, data, and phenomena, we present some new theoretical ideas and numerical results. We discuss among others the basic idea of the RSB theory, correlation functions, interfaces, overlaps, pure states, random field, and the dynamical approach. We present new numerical results for the behaviors of coupled replicas and about the numerical verification of sum rules, and we review some of the available numerical results that we consider of larger importance (for example, the determination of the phase transition point, the correlation functions, the window overlaps, and the dynamical behavior of the system).

In this talk we review our theoretical understanding of spin glasses paying a particular attention to the basic physical ideas. We introduce the replica method and we describe its probabilistic consequences (we stress the recently discovered importance of stochastic stability). We show that the replica method is not restricted to systems with quenched disorder. We present the consequences on the dynamics of the system when it slows approaches equilibrium are presented: they are confirmed by large scale simulations, while we are still awaiting for a direct experimental verification.

In these two lectures I review our theoretical understanding of spin glasses paying a particular attention to the basic physical ideas. We introduce the replica method and we describe its probabilistic consequences (we stress the recently discovered importance of stochastic stability). We show that the replica method is not restricted to systems with quenched disorder. We present the consequences on the dynamics of the system when it slows approaches equilibrium are presented: they are confirmed by large scale simulations, while we are still awaiting for a direct experimental

In the present Ph.D. dissertation I present results concerning disordered and frustrated models of relevance in statistical mechanics and in combinatorial optimization. As an application of spin glass theory I study the disordered and frustrated Blume-Emery-Griffiths model. The model is treated in its mean-field approximation using replicas. Within the Ansatz of replica-symmetry, I present a complete numerical solution; I also discuss effects of replica symmetry breaking. The stability of the RS solution is studied and the regions of instability inferred. The phase diagram exhibits first and second order transitions. The tricritical point is still present in the frustrated model, in agreement with former work. A version of the BEG model with disordered chemical potential is also studied. The calculations confirm that the disorder decreases the tricritical temperature. Next, I consider the graph partitioning problem, a combinatorial optimization problem, which, from the point of view of statistical mechanics is a spin glass model with the constraint of zero magnetisation. I focus on the statistical properties of low energy solutions generated by heuristic algorithms designed to solve such hard combinatorial optimization problems. Several heuristics proposed to solve this problem were implemented. Scaling laws are obtained; in particular, the average cost and its variance grow linearly with the number of vertices of the graphs. As a consequence the cost found by the heuristics is self-averaging. I suggest that this property is quite general, valid for random solutions, quasi-optimal solutions, and probably for the optimum solutions, too. Furthermore a ranking method is proposed and illustrated on an ensemble of graph partitioning problems. This ranking procedure takes into account the quality of the solution as well as the time necessary to find that solution. In the third part of this dissertation I study in detail the zero-temperatures properties of spin glasses on sparse random graphs with fixed connectivity. Spin glasses on these graphs may be considered as a more realistic approximation to real spin glasses as represented by the model of Sherrington and Kirkpatrick. I have designed a new algorithm for finding low energy states. Second, I present a method for deriving the ground state energy from heuristic algorithms, even though they are not guaranteed to find the optimum. Third, I present a numerical test of a conjecture due to Banavar, Sherrington and Sourlas, giving the large volume energy density of the ground states as function of the connectivity. The distribution of the order parameter is found to be non-trivial, and I give evidence for the presence of ultrametricity for all values of the connectivity. These results confirm the expectation that the remarquable properties of the infinite range Sherrington-Kirkpatrick model carry over to more realistic models, as for example the spin glass model on random graphs with finite connectivity studied in the present work.