Search PubMed⌕ Search

Biomedical subjects

F Ricci-Tersenghi

Publications and source records attributed to F Ricci-Tersenghi.

10 recordsLinked to original sources
PubMed2002

Hiding solutions in random satisfiability problems: a statistical mechanics approach.

A major problem in evaluating stochastic local search algorithms for NP-complete problems is the need for a systematic generation of hard test instances having previously known properties of the optimal solutions. On the basis of statistical mechanics results, we propose random generators of hard and satisfiable instances for the 3-satisfiability problem. The design of the hardest problem instances is based on the existence of a first order ferromagnetic phase transition and the glassy nature of excited states. The analytical predictions are corroborated by numerical results obtained from complete as well as stochastic local algorithms.

Algorithms↗
PubMed2001

Learning to coordinate in a complex and nonstationary world.

We study analytically and by computer simulations a complex system of adaptive agents with finite memory. Borrowing the framework of the minority game and using the replica formalism we show the existence of an equilibrium phase transition as a function of the ratio between the memory lambda and the learning rates Gamma of the agents. We show that, starting from a random configuration, a dynamic phase transition also exists, which prevents agents from reaching optimal coordination. Furthermore, in a nonstationary environment, we show by numerical simulations that the phase transition becomes discontinuous.

Game Theory↗
PubMed2001

Exact solutions for diluted spin glasses and optimization problems.

We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p = 3, gamma(d) = 0.818, and gamma(s) = 0.918), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds ( gamma(var)(c) = 4.396 and gamma(var)(c) = 2.149).

Journal Article↗
PubMed2001

Simplest random K-satisfiability problem.

We study a simple and exactly solvable model for the generation of random satisfiability problems. These consist of gammaN random boolean constraints which are to be satisfied simultaneously by N logical variables. In statistical-mechanics language, the considered model can be seen as a diluted p-spin model at zero temperature. While such problems become extraordinarily hard to solve by local search methods in a large region of the parameter space, still at least one solution may be superimposed by construction. The statistical properties of the model can be studied exactly by the replica method and each single instance can be analyzed in polynomial time by a simple global solution method. The geometrical and topological structures responsible for dynamic and static phase transitions as well as for the onset of computational complexity in the local search method are thoroughly analyzed. Numerical analysis on very large samples allows for a precise characterization of the critical scaling behavior.

Journal Article↗
PubMed2000

Two time scales and violation of the fluctuation-dissipation theorem in a finite dimensional model for structural glasses

We study the breakdown of fluctuation-dissipation relations between time-dependent density-density correlations and associated responses following a quench in the chemical potential in the frustrated Ising lattice gas. The corresponding slow dynamics is characterized by two well-separated time scales characterized by a constant value of the fluctuation-dissipation ratio. This result is particularly relevant since activated processes dominate the long-time dynamics of the system.

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↗
PubMed2000

Ultrametricity in three-dimensional edwards-anderson spin glasses

We perform an accurate test of ultrametricity in the aging dynamics of the three-dimensional Edwards-Anderson spin glass. Our method consists in considering the evolution in parallel of two identical systems constrained to have fixed overlap. This turns out to be a particularly efficient way to study the geometrical relations between configurations at distant large times. Our findings strongly hint towards dynamical ultrametricity in spin glasses, while this is absent in simpler aging systems with domain growth dynamics. A recently developed theory of linear response in glassy systems allows us to infer that dynamical ultrametricity implies the same property at the level of equilibrium states.

Journal Article↗
PubMed2000

Dynamics of the frustrated ising lattice gas

The dynamical properties of a three-dimensional model glass, the frustrated Ising lattice gas (FILG), are studied by Monte Carlo simulations. We present results of compression experiments, where the chemical potential is either slowly or abruptly changed, as well as simulations at constant density. One time quantities like density and two time quantities like correlations, responses, and mean square displacements are measured, and the departure from equilibrium clearly characterized. The aging scenario, particularly in the case of density autocorrelations, is reminiscent of spin glass phenomenology with violations of the fluctuation-dissipation theorem, typical of systems with one replica symmetry breaking. The FILG, as a valid on-lattice model of structural glasses, can be described with tools developed in spin glass theory and, being a finite-dimensional model, can open the way for a systematic study of activated processes in glasses.

Journal Article↗
PubMed2000

Glassy dynamics near zero temperature

We numerically study finite-dimensional spin glasses at low and zero temperature, finding evidence for (i) strong time-space heterogeneities, (ii) spontaneous time scale separation, and (iii) power law distributions of flipping times. Using zero temperature dynamics we study blocking, clustering and persistence phenomena.

Journal Article↗