Search PubMed⌕ Search

Biomedical subjects

R Zecchina

Publications and source records attributed to R Zecchina.

12 recordsLinked to original sources
PubMed2002

Analytic and algorithmic solution of random satisfiability problems.

We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio alpha of clauses to variables less than a threshold alphac are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below alphac, where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability.

Journal Article↗
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

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↗