title: Optimizing searches via rare events.
abstract: Randomized search algorithms for hard combinatorial problems exhibit a large variability of performances. We study the different types of rare events which occur in such out-of-equilibrium stochastic processes and we show how they cooperate in determining the final distribution of running times. As a by-product of our analysis we show how search algorithms are optimized by random restarts.
authors: Laboratoire de Physique Théorique de l'ENS, 24 rue Lhomond, 75231 Paris cedex 05, France. montanar@lpt.ens.fr
authors: Andrea
authors: A
authors: Montanari
authors: Riccardo
authors: R
authors: Zecchina