Random K-satisfiability problem: from an analytic solution to an efficient algorithm

We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the existence of an intermediate phase in the satisfiable region, where the proliferation of metastable states is at the origin of the slowdown of search algorithms. The fundamental order parameter introduced in the cavity method, which consists of surveys of local magnetic fields in the various possible states of the system, can be computed for one given sample. These surveys can be used to invent new types of algorithms for solving hard combinatorial optimizations problems. One such algorithm is shown here for the K=3 satisfiability problem, with very good performances.

The secondary structure of RNA under tension

We study the force-induced unfolding of random disordered RNA or single-stranded DNA polymers. The system undergoes a second-order phase transition from a collapsed globular phase at low forces to an extensive necklace phase with a macroscopic end-to-end distance at high forces. At low temperatures, the sequence inhomogeneities modify the critical behaviour. We provide numerical evidence for the universality of the critical exponents which, by extrapolation of the scaling laws to zero force, contain useful information on the ground-state (f = 0) properties. This provides a good method for quantitative studies of scaling exponents characterizing the collapsed globule. In order to get rid of the blurring effect of thermal fluctuations, we restrict ourselves to the ground state at fixed external force. We analyze the statistics of rearrangements, in particular below the critical force, and point out its implications for force-extension experiments on single molecules.

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.

Lattice glass models

Motivated by the concept of geometrical frustration, we introduce a class of statistical mechanics lattice models for the glass transition. Monte Carlo simulations in three dimensions show that they display a dynamical glass transition which is very similar to that observed in other off-lattice systems and which does not depend on a specific dynamical rule. A mean-field study shows the existence of a discontinuous glass transition, in agreement with the numerical observations.

Hairpin formation and elongation of biomolecules

We introduce a model of thermalized conformations in space of RNA-or single stranded DNA-molecules, which includes the possibility of hairpin formation. This model contains the usual secondary structure information, but extends it to the study of one element of the ternary structure, namely the end-to-end distance. The computed force-elongation characteristics are in good agreement with some recent measurements on single stranded DNA molecules.

Wandering of a contact line at thermal equilibrium

We reconsider the problem of the solid-liquid-vapor contact-line on a disordered substrate, in the collective pinning regime. We perform a replica variational calculation which confirms the scaling behavior obtained from Larkin-Imry-Ma-like arguments and provides a quantitative prediction for the correlation function of the line. This prediction is in good agreement with experimental findings for the case of superfluid helium on a caesium substrate.