Biomedical subjects

A Pagnani

Publications and source records attributed to A Pagnani.

8 recordsLinked to original sources

PubMed2006

Core percolation and onset of complexity in boolean networks.

The determination and classification of fixed points of large Boolean networks is addressed in terms of a constraint-satisfaction problem. We develop a general simplification scheme that, removing all those variables and functions belonging to trivial logical cascades, returns the computational core of the network. The transition line from an easy to a complex regulatory phase is described as a function of the parameters of the model, identifying thereby both theoretically and algorithmically the relevant regulatory variables.

Algorithms↗

PubMed2003

Near-optimal configurations in mean-field disordered systems.

We present a general technique to compute how the energy of a configuration varies as a function of its overlap with the ground state in the case of optimization problems. Our approach is based on a generalization of the cavity method to a system interacting with its ground state. With this technique we study the random matching problem as well as the mean-field diluted spin glass. As a by-product of this approach we calculate the de Almeida-Thouless transition line of the spin glass on a fixed connectivity random graph.

Journal Article↗

PubMed2003

Polynomial iterative algorithms for coloring and analyzing random graphs.

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c in [c(d),c(q)].

Journal Article↗

PubMed2003

Scalings of domain wall energies in two dimensional Ising spin glasses.

We study domain wall energies of two dimensional spin glasses. The scaling of these energies depends on the model's distribution of quenched random couplings, falling into three different classes. The first class is associated with the exponent theta approximately -0.28; the other two classes have theta=0, as can be justified theoretically. In contrast to previous claims, we find that theta=0 does not indicate d=d(c)(l) but rather d< or =d(c)(l), where d(c)(l) is the lower critical dimension.

Journal Article↗

PubMed2003

Metastable configurations on the Bethe lattice.

We present a general analytic method to compute the number of metastable configurations as a function of the energy for a system of interacting Ising spins on the Bethe lattice. Our approach is based on the cavity method. We apply it to the case of ferromagnetic interactions, and also to the binary and Gaussian spin glasses. Most of our results are obtained within the replica symmetric ansatz, but we illustrate how replica symmetry breaking can be performed.

Journal Article↗

PubMed2002

Coloring random graphs.

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring, whereas graphs with high connectivity are uncolorable. Depending on q, we find the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.

Journal Article↗

PubMed2002

Width distributions and the upper critical dimension of Kardar-Parisi-Zhang interfaces.

Simulations of restricted solid-on-solid growth models are used to build the width distributions of d=2-5 dimensional Kardar-Parisi-Zhang (KPZ) interfaces. We find that the universal scaling function associated with the steady-state width distribution changes smoothly as d is increased, thus strongly suggesting that d=4 is not an upper critical dimension for the KPZ equation. The dimensional trends observed in the scaling functions indicate that the upper critical dimension is at infinity.

Journal Article↗

PubMed2000

Glassy transition in a disordered model for the RNA secondary structure.

We numerically study a disordered model for the RNA secondary structure and we find that it undergoes a phase transition, with a breaking of the replica symmetry in the low temperature region (as in spin glasses). Our results are based on the exact evaluation of the partition function.

Models, Chemical↗