Search

We compute spectra of symmetric random matrices describing graphs with general modular structure and arbitrary inter- and intra-module degree distributions, subject only to the constraint of finite mean connectivities. We also evaluate spectra of a certain class of small-world matrices generated from random graphs by introducing short-cuts via additional random connectivity components. Both adjacency matrices and the associated graph Laplacians are investigated. For the Laplacians, we find Lifshitz type singular behaviour of the spectral density in a localised region of small $|\lambda|$ values. In the case of modular networks, we can identify contributions local densities of state from individual modules. For small-world networks, we find that the introduction of short cuts can lead to the creation of satellite bands outside the central band of extended states, exhibiting only localised states in the band-gaps. Results for the ensemble in the thermodynamic limit are in excellent agreement with those obtained via a cavity approach for large finite single instances, and with direct diagonalisation results., Comment: 18 pages, 5 figures

We study a variation of the graph colouring problem on random graphs of finite average connectivity. Given the number of colours, we aim to maximise the number of different colours at neighbouring vertices (i.e. one edge distance) of any vertex. Two efficient algorithms, belief propagation and Walksat are adapted to carry out this task. We present experimental results based on two types of random graphs for different system sizes and identify the critical value of the connectivity for the algorithms to find a perfect solution. The problem and the suggested algorithms have practical relevance since various applications, such as distributed storage, can be mapped onto this problem., Comment: 10 pages, 10 figures

We obtain exact expressions for the asymptotic behaviour of the average probability of the block decoding error for ensembles of regular low density parity check error correcting codes, by employing diagrammatic techniques. Furthermore, we show how imposing simple constraints on the code ensemble (that can be practically implemented in linear time), allows one to suppress the error probability for codes with more than 2 checks per bit, to an arbitrarily low power of $N$. As such we provide a practical route to a (sub-optimal){\em expurgated} ensemble., Comment: 15 pages 13 figures

We present a theoretical method for a direct evaluation of the average and reliability error exponents in low-density parity-check error-correcting codes using methods of statistical physics. Results for the binary symmetric channel (BSC) are presented for codes of both finite and infinite connectivity., Comment: 13 pages, 5 figures

Using the magnetization enumerator method, we evaluate the practical and theoretical limitations of symmetric channels with real outputs. Results are presented for several regular Gallager code constructions., Comment: 5 pages, 1 figure, to appear as Brief Report in Physical Review E

The problem of vertex coloring in random graphs is studied using methods of statistical physics and probability. Our analytical results are compared to those obtained by exact enumeration and Monte-Carlo simulations. We critically discuss the merits and shortcomings of the various methods, and interpret the results obtained. We present an exact analytical expression for the 2-coloring problem as well as general replica symmetric approximated solutions for the thermodynamics of the graph coloring problem with p colors and K-body edges., Comment: 17 pages, 9 figures

We determine the critical noise level for decoding low density parity check error correcting codes based on the magnetization enumerator ($\cM$), rather than on the weight enumerator ($\cW$) employed in the information theory literature. The interpretation of our method is appealingly simple, and the relation between the different decoding schemes such as typical pairs decoding, MAP, and finite temperature decoding (MPM) becomes clear. In addition, our analysis provides an explanation for the difference in performance between MN and Gallager codes. Our results are more optimistic than those derived via the methods of information theory and are in excellent agreement with recent results from another statistical physics approach., Comment: 9 pages, 5 figures

We propose a method to determine the critical noise level for decoding Gallager type low density parity check error correcting codes. The method is based on the magnetization enumerator ($\cM$), rather than on the weight enumerator ($\cW$) presented recently in the information theory literature. The interpretation of our method is appealingly simple, and the relation between the different decoding schemes such as typical pairs decoding, MAP, and finite temperature decoding (MPM) becomes clear. Our results are more optimistic than those derived via the methods of information theory and are in excellent agreement with recent results from another statistical physics approach., Comment: 10 pages, 4 figures, 8th IMA int. conf. on cryptography and Coding

In this paper we analyse both the dynamics and the high density physics of the infinite dimensional lattice gas model for random heteropolymers recently introduced in \cite{jort}. Restricting ourselves to site-disordered heteropolymers, we derive exact closed deterministic evolution equations for a suitable set of dynamic order parameters (in the thermodynamic limit), and use these to study the dynamics of the system for different choices of the monomer polarity parameters. We also study the equilibrium properties of the system in the high density limit, which leads to a phase diagram exhibiting transitions between swollen states, compact states, and regions with partial compactification. Our results find excellent verification in numerical simulations, and have a natural and appealing interpretation in terms of real heteropolymers., Comment: 12 pages, 8 eps figures, revised version (to be published in EPJ)

We propose and solve a simple model describing secondary structure formation in random hetero-polymers. It describes monomers with a combination of one-dimensional short-range interactions (representing steric forces and hydrogen bonds) and infinite range interactions (representing polarity forces). We solve our model using a combination of mean field and random field techniques, leading to phase diagrams exhibiting second-order transitions between folded, partially folded and unfolded states, including regions where folding depends on initial conditions. Our theoretical results, which are in excellent agreement with numerical simulations, lead to an appealing physical picture of the folding process: the polarity forces drive the transition to a collapsed state, the steric forces introduce monomer specificity, and the hydrogen bonds stabilise the conformation by damping the frustration-induced multiplicity of states., Comment: 24 pages, 14 figures

We propose a general scheme in which disordered systems are allowed to sacrifice energy equi-partitioning and separate into a hierarchy of ergodic sub-systems (clusters) with different characteristic time-scales and temperatures. The details of the break-up follow from the requirement of stationarity of the entropy of the slower cluster, at every level in the hierarchy. We apply our ideas to the Sherrington-Kirkpatrick model, and show how the Parisi solution can be {\it derived} quantitatively from plausible physical principles. Our approach gives new insight into the physics behind Parisi's solution and its relations with other theories, numerical experiments, and short range models., Comment: 7 pages 5 figures

We propose a general quantitative scheme in which systems are given the freedom to sacrifice energy equi-partitioning on the relevant time-scales of observation, and have phase transitions by separating autonomously into ergodic sub-systems (clusters) with different characteristic time-scales and temperatures. The details of the break-up follow uniquely from the requirement of zero entropy for the slower cluster. Complex systems, such as the Sherrington-Kirkpatrick model, are found to minimise their free energy by spontaneously decomposing into a hierarchy of ergodically equilibrating degrees of freedom at different (effective) temperatures. This leads exactly and uniquely to Parisi's replica symmetry breaking scheme. Our approach, which is somewhat akin to an earlier one by Sompolinsky, gives new insight into the physical interpretation of the Parisi scheme and its relations with other approaches, numerical experiments, and short range models. Furthermore, our approach shows that the Parisi scheme can be derived quantitatively and uniquely from plausible physical principles., Comment: 6 pages, 3 figures, proceedings of international conference on "Disordered And Complex Systems", 10-14 July 2000 King's College London

A model of noise reduction (NR) for signal processing is introduced. Each noise source puts a symmetric constraint on the space of the signal vector within a tolerable overlap. When the number of noise sources increases, sequences of transitions take place, causing the solution space to vanish. We found that the transition from an extended solution space to a shrunk space is retarded because of the symmetry of the constraints, in contrast to the analogous problem of pattern storage. For low tolerance, the solution space vanishes by volume reduction, whereas for high tolerance, the vanishing becomes more and more like percolation. The model is studied in the replica symmetric, first step and full replica symmetry breaking schemes., Comment: 4 pages, 2 figures

A lattice model of a hetero-polymer with random hydrophilic-hydrophobic charges interacting with the solvent is introduced, whose continnuum counterpart has been proposed by T. Garel, L. Leibler and H. Orland {J. Phys. II France 4, 2139 (1994)]. The transfer matrix technique is used to study various constrained annealed systems which approximate at various degrees of accuracy the original quenched model. For highly hydrophobic chains an ordinary $\theta$-point transition is found from a high temperature swollen phase to a low temperature compact phase. Depending on the type of constrained averages, at very low temperatures a swollen phase or a coexistence between compact and swollen phases are found. The results are carefully compared with the corresponding ones obtained in the continuum limit, and various improvements in the original calculations are discussed., Comment: 13 pages, 8 figures; revised version with minor changes, accepted for publication in European Physical Journal B