Boosting search by rare events
<|reference_start|>Boosting search by rare events: 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 byproduct of our analysis we show how search algorithms are optimized by random restarts.<|reference_end|>
@article{montanari2001boosting,
    title={Boosting search by rare events},
    author={Andrea Montanari and Riccardo Zecchina},
    journal={Phys. Rev. Lett. 88, 178701 (2002)},
    year={2001},
    doi={10.1103/PhysRevLett.88.178701},
    archivePrefix={arXiv},
    eprint={cond-mat/0112142},
    primaryClass={cond-mat.stat-mech cond-mat.dis-nn cs.CC}
}