Statistical mechanics and combinatorial problems

Marc Mézard, Riccardo Zecchina, Random K -satisfiability problem: From an analytic solution to an efficient algorithm Physical Review E. ,vol. 66, pp. 056126- ,(2002) , 10.1103/PHYSREVE.66.056126

Jacques Distler, A note on the three-dimensional Ising model as a string theory Nuclear Physics. ,vol. 388, pp. 648- 670 ,(1992) , 10.1016/0550-3213(92)90558-S

Marc Mézard, Giorgio Parisi, Riccardo Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems Science. ,vol. 297, pp. 812- 815 ,(2002) , 10.1126/SCIENCE.1073287

Ehud Friedgut, appendix by Jean Bourgain, Sharp thresholds of graph properties, and the -sat problem Journal of the American Mathematical Society. ,vol. 12, pp. 1017- 1054 ,(1999) , 10.1090/S0894-0347-99-00305-7

Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky, Determining computational complexity from characteristic 'phase transitions.' Nature. ,vol. 400, pp. 133- 137 ,(1999) , 10.1038/22055

M. Mézard, G. Parisi, The Bethe lattice spin glass revisited European Physical Journal B. ,vol. 20, pp. 217- 233 ,(2001) , 10.1007/PL00011099

M. Mézard, T. Mora, R. Zecchina, Clustering of solutions in the random satisfiability problem. Physical Review Letters. ,vol. 94, pp. 197205- ,(2005) , 10.1103/PHYSREVLETT.94.197205

Mark Jerrum, Alistair Sinclair, Approximating the permanent SIAM Journal on Computing. ,vol. 18, pp. 1149- 1178 ,(1989) , 10.1137/0218077

Simona Cocco, Rémi Monasson, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances Theoretical Computer Science. ,vol. 320, pp. 345- 372 ,(2004) , 10.1016/J.TCS.2004.02.034

Dimitris Achlioptas, Assaf Naor, Yuval Peres, Rigorous location of phase transitions in hard optimization problems Nature. ,vol. 435, pp. 759- 764 ,(2005) , 10.1038/NATURE03602