PubMed Health⌕ Search

Biomedical subjects

R Zecchina

Publications and source records attributed to R Zecchina.

10 recordsLinked to original sources
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

Statistical mechanics of systems with heterogeneous agents: minority games

We study analytically a simple game theoretical model of heterogeneous interacting agents. We show that the stationary state of the system is described by the ground state of a disordered spin model which is exactly solvable within the simple replica symmetric ansatz. Such a stationary state differs from the Nash equilibrium where each agent maximizes her own utility. The latter turns out to be characterized by a replica symmetry broken structure. Numerical results fully agree with our analytical findings.

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↗