Statistical physics of inference: Thresholds and algorithms
Many questions of fundamental interest in today's science can be formulated as inference
problems: some partial, or noisy, observations are performed over a set of variables and the …
problems: some partial, or noisy, observations are performed over a set of variables and the …
Optimization using quantum mechanics: quantum annealing through adiabatic evolution
We review here some recent work in the field of quantum annealing, alias adiabatic
quantum computation. The idea of quantum annealing is to perform optimization by a …
quantum computation. The idea of quantum annealing is to perform optimization by a …
Survey propagation: An algorithm for satisfiability
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 …
literals over N Boolean variables. For a given value of N the problem is known to be most …
Random -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 …
variables. Using the cavity method at zero temperature, we find the phase diagram for the K …
[BOOK][B] An introduction to metaheuristics for optimization
B Chopard, M Tomassini - 2018 - Springer
Heuristic methods are used when rigorous ones are either unknown or cannot be applied,
typically because they would be too slow. A metaheuristic is a general optimization …
typically because they would be too slow. A metaheuristic is a general optimization …
Proof of the satisfiability conjecture for large k
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 …
limiting density αs (k) such that a random k-SAT formula of clause density α is with high …
The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective
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 …
with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to …
Threshold values of random K‐SAT from the cavity method
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 …
Mézard and Zecchina, Phys Rev E 66 (2002), 056126 we derive the various threshold …
Optimization hardness as transient chaos in an analog approach to constraint satisfaction
Boolean satisfiability (k-SAT) is one of the most studied optimization problems, as an
efficient (that is, polynomial-time) solution to k-SAT (for k≥ 3) implies efficient solutions to a …
efficient (that is, polynomial-time) solution to k-SAT (for k≥ 3) implies efficient solutions to a …
Spintronics-compatible approach to solving maximum-satisfiability problems with probabilistic computing, invertible logic, and parallel tempering
The search for hardware-compatible strategies for solving nondeterministic polynomial time
(NP)-hard combinatorial optimization problems (COPs) is an important challenge of today's …
(NP)-hard combinatorial optimization problems (COPs) is an important challenge of today's …