14 citations · 15 across the 3 of their papers we have counts for
6 papers
Approximate analysis of search algorithms with "physical" methods
Simona Cocco, Remi Monasson, Andrea Montanari +1
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, d…
Restart method and exponential acceleration of random 3-SAT instances resolutions: a large deviation analysis of the Davis-Putnam-Loveland-Logemann algorithm
S. Cocco, R. Monasson
The analysis of the solving complexity of random 3-SAT instances using the Davis-Putnam-Loveland-Logemann (DPLL) algorithm slightly below threshold is presented. While finding a so…
Theoretical models for single-molecule DNA and RNA experiments: from elasticity to unzipping
S. Cocco, J. F. Marko, R. Monasson
We review statistical-mechanical theories of single-molecule micromanipulation experiments on nucleic acids. First, models for describing polymer elasticity are introduced. We then…
Statistical mechanics methods and phase transitions in optimization problems
O. C. Martin, R. Monasson, R. Zecchina
Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many…
2+p-SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition
R. Monasson, R. Zecchina, S. Kirkpatrick +2
Heuristic methods for solution of problems in the NP-Complete class of decision problems often reach exact solutions, but fail badly at "phase boundaries", across which the decisio…
Learning and generalization theories of large committee--machines
Remi Monasson, Riccardo Zecchina
The study of the distribution of volumes associated to the internal representations of learning examples allows us to derive the critical learning capacity ($α_c=\frac{16}π \sqrt{\…