Darcy's law of yield stress fluids on a treelike network.

Understanding the flow of yield stress fluids in porous media is a major challenge. In particular, experiments and extensive numerical simulations report a nonlinear Darcy law as a function of the pressure gradient. In this letter we consider a treelike porous structure for which the problem of the flow can be resolved exactly due to a mapping with the directed polymer (DP) with disordered bond energies on the Cayley tree. Our results confirm the nonlinear behavior of the flow and expresses its full pressure dependence via the density of low-energy paths of DP restricted to vanishing overlap. These universal predictions are confirmed by extensive numerical simulations.

Jamming in Multilayer Supervised Learning Models.

Critical jamming transitions are characterized by an astonishing degree of universality. Analytic and numerical evidence points to the existence of a large universality class that encompasses finite and infinite dimensional spheres and continuous constraint satisfaction problems (CCSP) such as the nonconvex perceptron and related models. In this Letter we investigate multilayer neural networks (MLNN) learning random associations as models for CCSP that could potentially define different jamming universality classes. As opposed to simple perceptrons and infinite dimensional spheres, which are described by a single effective field in terms of which the constraints appear to be one dimensional, the description of MLNN involves multiple fields, and the constraints acquire a multidimensional character. We first study the models numerically and show that similarly to the perceptron, whenever jamming is isostatic, the sphere universality class is recovered, we then write the exact mean-field equations for the models and identify a dimensional reduction mechanism that leads to a scaling regime identical to the one of spheres.

Critical Jammed Phase of the Linear Perceptron.

Criticality in statistical physics naturally emerges at isolated points in the phase diagram. Jamming of spheres is not an exception: varying density, it is the critical point that separates the unjammed phase where spheres do not overlap and the jammed phase where they cannot be arranged without overlaps. The same remains true in more general constraint satisfaction problems with continuous variables where jamming coincides with the (protocol dependent) satisfiability transition point. In this work we show that by carefully choosing the cost function to be minimized, the region of criticality extends to occupy a whole region of the jammed phase. As a working example, we consider the spherical perceptron with a linear cost function in the unsatisfiable jammed phase and we perform numerical simulations which show critical power laws emerging in the configurations obtained minimizing the linear cost function. We develop a scaling theory to compute the emerging critical exponents.

Gardner physics in amorphous solids and beyond.

One of the most remarkable predictions to emerge out of the exact infinite-dimensional solution of the glass problem is the Gardner transition. Although this transition was first theoretically proposed a generation ago for certain mean-field spin glass models, its materials relevance was only realized when a systematic effort to relate glass formation and jamming was undertaken. A number of nontrivial physical signatures associated with the Gardner transition have since been considered in various areas, from models of structural glasses to constraint satisfaction problems. This perspective surveys these recent advances and discusses the novel research opportunities that arise from them.

Impact of jamming criticality on low-temperature anomalies in structural glasses.

We present a mechanism for the anomalous behavior of the specific heat in low-temperature amorphous solids. The analytic solution of a mean-field model belonging to the same universality class as high-dimensional glasses, the spherical perceptron, suggests that there exists a cross-over temperature above which the specific heat scales linearly with temperature, while below it, a cubic scaling is displayed. This relies on two crucial features of the phase diagram: (i) the marginal stability of the free-energy landscape, which induces a gapless phase responsible for the emergence of a power-law scaling; and (ii) the vicinity of the classical jamming critical point, as the cross-over temperature gets lowered when approaching it. This scenario arises from a direct study of the thermodynamics of the system in the quantum regime, where we show that, contrary to crystals, the Debye approximation does not hold.

Constraint satisfaction mechanisms for marginal stability and criticality in large ecosystems.

We discuss a resource-competition model, which takes MacArthur's model as a platform, to unveil interesting connections with glassy features and jamming in high dimensions. This model, as first studied by Tikhonov and Monasson, presents two qualitatively different phases: a shielded phase, where a collective, self-sustained behavior emerges, and a vulnerable phase, where a small perturbation can destabilize the system and contribute to population extinction. We first present our perspective based on a strong similarity with continuous constraint satisfaction problems in their convex regime. Then, we discuss the stability analysis in terms of the computation of the leading eigenvalue of the Hessian matrix of the associated Lyapunov function. This computation allows us to efficiently distinguish between the two aforementioned phases and to relate high-dimensional critical ecosystems to glassy phenomena in the low-temperature regime.

Matrix product algorithm for stochastic dynamics on networks applied to nonequilibrium Glauber dynamics.

We introduce and apply an efficient method for the precise simulation of stochastic dynamical processes on locally treelike graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, our approach is based on a matrix product approximation of the so-called edge messages-conditional probabilities of vertex variable trajectories. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the matrix product edge messages (MPEM) in truncations. In contrast to Monte Carlo simulations, the algorithm has a better error scaling and works for both single instances as well as the thermodynamic limit. We employ it to examine prototypical nonequilibrium Glauber dynamics in the kinetic Ising model. Because of the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations.

Random-diluted triangular plaquette model: Study of phase transitions in a kinetically constrained model.

We study how the thermodynamic properties of the triangular plaquette model (TPM) are influenced by the addition of extra interactions. The thermodynamics of the original TPM is trivial, while its dynamics is glassy, as usual in kinetically constrained models. As soon as we generalize the model to include additional interactions, a thermodynamic phase transition appears in the system. The additional interactions we consider are either short ranged, forming a regular lattice in the plane, or long ranged of the small-world kind. In the case of long-range interactions we call the new model the random-diluted TPM. We provide arguments that the model so modified should undergo a thermodynamic phase transition, and that in the long-range case this is a glass transition of the "random first-order" kind. Finally, we give support to our conjectures studying the finite-temperature phase diagram of the random-diluted TPM in the Bethe approximation. This corresponds to the exact calculation on the random regular graph, where free energy and configurational entropy can be computed by means of the cavity equations.

Identifying relevant positions in proteins by Critical Variable Selection.

Evolution in its course has found a variety of solutions to the same optimisation problem. The advent of high-throughput genomic sequencing has made available extensive data from which, in principle, one can infer the underlying structure on which biological functions rely. In this paper, we present a new method aimed at the extraction of sites encoding structural and functional properties from a set of protein primary sequences, namely a multiple sequence alignment. The method, called critical variable selection, is based on the idea that subsets of relevant sites correspond to subsequences that occur with a particularly broad frequency distribution in the dataset. By applying this algorithm to in silico sequences, to the response regulator receiver and to the voltage sensor domain of ion channels, we show that this procedure recovers not only the information encoded in single site statistics and pairwise correlations but also captures dependencies going beyond pairwise correlations. The method proposed here is complementary to statistical coupling analysis, in that the most relevant sites predicted by the two methods differ markedly. We find robust and consistent results for datasets as small as few hundred sequences that reveal a hidden hierarchy of sites that are consistent with the present knowledge on biologically relevant sites and evolutionary dynamics. This suggests that critical variable selection is capable of identifying a core of sites encoding functional and structural information in a multiple sequence alignment.

The Edge-Disjoint Path Problem on Random Graphs by Message-Passing.

We present a message-passing algorithm to solve a series of edge-disjoint path problems on graphs based on the zero-temperature cavity equations. Edge-disjoint paths problems are important in the general context of routing, that can be defined by incorporating under a unique framework both traffic optimization and total path length minimization. The computation of the cavity equations can be performed efficiently by exploiting a mapping of a generalized edge-disjoint path problem on a star graph onto a weighted maximum matching problem. We perform extensive numerical simulations on random graphs of various types to test the performance both in terms of path length minimization and maximization of the number of accommodated paths. In addition, we test the performance on benchmark instances on various graphs by comparison with state-of-the-art algorithms and results found in the literature. Our message-passing algorithm always outperforms the others in terms of the number of accommodated paths when considering non trivial instances (otherwise it gives the same trivial results). Remarkably, the largest improvement in performance with respect to the other methods employed is found in the case of benchmarks with meshes, where the validity hypothesis behind message-passing is expected to worsen. In these cases, even though the exact message-passing equations do not converge, by introducing a reinforcement parameter to force convergence towards a sub optimal solution, we were able to always outperform the other algorithms with a peak of 27% performance improvement in terms of accommodated paths. On random graphs, we numerically observe two separated regimes: one in which all paths can be accommodated and one in which this is not possible. We also investigate the behavior of both the number of paths to be accommodated and their minimum total length.

Universal spectrum of normal modes in low-temperature glasses.

We report an analytical study of the vibrational spectrum of the simplest model of jamming, the soft perceptron. We identify two distinct classes of soft modes. The first kind of modes are related to isostaticity and appear only in the close vicinity of the jamming transition. The second kind of modes instead are present everywhere in the glass phase and are related to the hierarchical structure of the potential energy landscape. Our results highlight the universality of the spectrum of normal modes in disordered systems, and open the way toward a detailed analytical understanding of the vibrational spectrum of low-temperature glasses.

Dynamics and termination cost of spatially coupled mean-field models.

This work is motivated by recent progress in information theory and signal processing where the so-called spatially coupled design of systems leads to considerably better performance. We address relevant open questions about spatially coupled systems through the study of a simple Ising model. In particular, we consider a chain of Curie-Weiss models that are coupled by interactions up to a certain range. Indeed, it is well known that the pure (uncoupled) Curie-Weiss model undergoes a first-order phase transition driven by the magnetic field, and furthermore in the spinodal region such systems are unable to reach equilibrium in subexponential time if initialized in the metastable state. In contrast, the spatially coupled system is instead able to reach the equilibrium even when initialized to the metastable state. The equilibrium phase propagates along the chain in the form of a traveling wave. Here we study the speed of the wave front and the so-called termination cost-i.e., the conditions necessary for the propagation to occur. We reach several interesting conclusions about optimization of the speed and the cost.

Static replica approach to critical correlations in glassy systems.

We discuss the slow relaxation phenomenon in glassy systems by means of replicas by constructing a static field theory approach to the problem. At the mean field level we study how criticality in the four point correlation functions arises because of the presence of soft modes and we derive an effective replica field theory for these critical fluctuations. By using this at the gaussian level we obtain many physical quantities: the correlation length, the exponent parameter that controls the mode-coupling dynamical exponents for the two-point correlation functions, and the prefactor of the critical part of the four point correlation functions. Moreover, we perform a one-loop computation in order to identify the region in which the mean field gaussian approximation is valid. The result is a Ginzburg criterion for the glass transition. We define and compute in this way a proper Ginzburg number. Finally, we present numerical values of all these quantities obtained from the hypernetted chain approximation for the replicated liquid theory.

A note on weakly discontinuous dynamical transitions.

We analyze mode coupling discontinuous transition in the limit of vanishing discontinuity, approaching the so called "A(3)" point. In these conditions structural relaxation and fluctuations appear to have universal form independent from the details of the system. The analysis of this limiting case suggests new ways for looking at the mode coupling equations in the general case.

Quantitative field theory of the glass transition.

We develop a full microscopic replica field theory of the dynamical transition in glasses. By studying the soft modes that appear at the dynamical temperature, we obtain an effective theory for the critical fluctuations. This analysis leads to several results: we give expressions for the mean field critical exponents, and we analytically study the critical behavior of a set of four-points correlation functions, from which we can extract the dynamical correlation length. Finally, we can obtain a Ginzburg criterion that states the range of validity of our analysis. We compute all these quantities within the hypernetted chain approximation for the Gibbs free energy, and we find results that are consistent with numerical simulations.

Using affinity propagation for identifying subspecies among clonal organisms: lessons from M. tuberculosis.

BACKGROUND: Classification and naming is a key step in the analysis, understanding and adequate management of living organisms. However, where to set limits between groups can be puzzling especially in clonal organisms. Within the Mycobacterium tuberculosis complex (MTC), the etiological agent of tuberculosis (TB), experts have first identified several groups according to their pattern at repetitive sequences, especially at the CRISPR locus (spoligotyping), and to their epidemiological relevance. Most groups such as "Beijing" found good support when tested with other loci. However, other groups such as T family and T1 subfamily (belonging to the "Euro-American" lineage) correspond to non-monophyletic groups and still need to be refined. Here, we propose to use a method called Affinity Propagation that has been successfully used in image categorization to identify relevant patterns at the CRISPR locus in MTC. RESULTS: To adequately infer the relative divergence time between strains, we used a distance method inspired by the recent evolutionary model by Reyes et al. We first confirm that this method performs better than the Jaccard index commonly used to compare spoligotype patterns. Second, we document the support of each spoligotype family among the previous classification using affinity propagation on the international spoligotyping database SpolDB4. This allowed us to propose a consensus assignation for all SpolDB4 spoligotypes. Third, we propose new signatures to subclassify the T family. CONCLUSION: Altogether, this study shows how the new clustering algorithm Affinity Propagation can help building or refining clonal organims classifications. It also describes well-supported families and subfamilies among M. tuberculosis complex, especially inside the modern "Euro-American" lineage.

Hierarchical random energy model of a spin glass.

We introduce a random energy model on a hierarchical lattice where the interaction strength between variables is a decreasing function of their mutual hierarchical distance, making it a non-mean-field model. Through small coupling series expansion and a direct numerical solution of the model, we provide evidence for a spin-glass condensation transition similar to the one occurring in the usual mean-field random energy model. At variance with the mean field, the high temperature branch of the free-energy is nonanalytic at the transition point.

Kac limit for finite-range spin glasses.

We consider a finite-range spin glass model in arbitrary dimension, where the strength of the two-body coupling decays to zero over some distance gamma(-1). We show that, under mild assumptions on the interaction potential, the infinite-volume free energy of the system converges to that of the Sherrington-Kirkpatrick one, in the Kac limit gamma-->0. This could be a first step toward an expansion around mean-field theory, for spin glass systems.