Search PubMed⌕ Search

Biomedical subjects

M Mézard

Publications and source records attributed to M Mézard.

15 recordsLinked to original sources
PubMed2005

Clustering of solutions in the random satisfiability problem.

Using elementary rigorous methods we prove the existence of a clustered phase in the random K-SAT problem, for K > or = 8. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.

Journal Article↗
PubMed2004

Frozen glass phase in the multi-index matching problem.

The multi-index matching is an NP-hard combinatorial optimization problem; for two indices it reduces to the well understood bipartite matching problem that belongs to the polynomial complexity class. We use the cavity method to solve the thermodynamics of the multi-index system with random costs. The phase diagram is much richer than for the case of the bipartite matching problem: it shows a finite temperature phase transition to a completely frozen glass phase, similar to what happens in the random energy model. We derive the critical temperature, the ground-state energy density, and properties of the energy landscape and compare the results to numerics based on exact analysis of small systems.

Journal Article↗
PubMed2004

Glassy phases in random heteropolymers with correlated sequences.

We develop an analytic approach for the study of lattice heteropolymers and apply it to copolymers with correlated Markovian sequences. According to our analysis, heteropolymers present three different dense phases depending upon the temperature, the nature of the monomer interactions, and the sequence correlations: (i) a liquid phase, (ii) a "soft glass" phase, and (iii) a "frozen glass" phase. The presence of the intermediate "soft glass" phase is predicted, for instance, in the case of polyampholytes with sequences that favor the alternation of monomers. Our approach is based on the cavity method, a refined Bethe-Peierls approximation adapted to frustrated systems. It amounts to a mean-field treatment in which the nearest-neighbor correlations, which are crucial in the dense phases of heteropolymers, are handled exactly. This approach is powerful and versatile; it can be improved systematically and generalized to other polymeric systems.

Journal Article↗
PubMed2004

Phase diagram of random heteropolymers.

We propose a new analytic approach to study the phase diagram of random heteropolymers, based on the cavity method. For copolymers we analyze the nature and phenomenology of the glass transition as a function of sequence correlations. Depending on these correlations, we find that two different scenarios for the glass transition can occur. We show that, beside the much studied possibility of an abrupt freezing transition at low temperature, the system can exhibit, upon cooling, a first transition to a soft glass phase with fully broken replica symmetry and a continuously growing degree of freezing as the temperature is lowered.

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

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.

Journal Article↗
PubMed2001

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.

DNA, Single-Stranded↗
PubMed1999

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.

Journal Article↗