Approximate analysis of search algorithms with "physical" methods
<|reference_start|>Approximate analysis of search algorithms with "physical" methods: An overview of some methods of statistical physics applied to the analysis of algorithms for optimization problems (satisfiability of Boolean constraints, vertex cover of graphs, decoding, ...) with distributions of random inputs is proposed. Two types of algorithms are analyzed: complete procedures with backtracking (Davis-Putnam-Loveland-Logeman algorithm) and incomplete, local search procedures (gradient descent, random walksat, ...). The study of complete algorithms makes use of physical concepts such as phase transitions, dynamical renormalization flow, growth processes, ... As for local search procedures, the connection between computational complexity and the structure of the cost function landscape is questioned, with emphasis on the notion of metastability.<|reference_end|>
@article{cocco2003approximate,
    title={Approximate analysis of search algorithms with "physical" methods},
    author={Simona Cocco, Remi Monasson, Andrea Montanari, Guilhem Semerjian},
    journal={arXiv preprint arXiv:cs/0302003},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0302003},
    primaryClass={cs.CC cond-mat.stat-mech}
}