Among various algorithms designed to exploit the specific properties of quantum computers
with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to …

We study the satisfiability of randomly generated formulas formed by M clauses of exactly K
literals over N Boolean variables. For a given value of N the problem is known to be most …

We present a fascinating model that has lately caught attention among physicists working in
complexity related fields. Though it originated from mathematics and later from economics …

This is a new, completely revised, updated and enlarged edition of the author's Ergebnisse
vol. 46:" Spin Glasses: A Challenge for Mathematicians". This new edition will appear in two …

We establish the satisfiability threshold for random k-SAT for all k≥ k0. That is, there exists a
limiting density αs (k) such that a random k-SAT formula of clause density α is with high …

In recent years important progress has been achieved towards proving the validity of the
replica predictions for the (asymptotic) mutual information (or “free energy”) in Bayesian …

Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we
establish a formula for the mutual information in statistical inference problems induced by …

Denote by A the adjacency matrix of an Erdos-Renyi graph with bounded average degree.
We consider the problem of maximizing< A-EA, X> over the set of positive semidefinite …

Using the cavity equations of Mézard, Parisi, and Zecchina Science 297 (2002), 812;
Mézard and Zecchina, Phys Rev E 66 (2002), 056126 we derive the various threshold …

For Erdős–Rényi random graphs with average degree γ, and uniformly random γ-regular
graph on n vertices, we prove that with high probability the size of both the Max-Cut and …