Exact solutions for diluted spin glasses and optimization problems - art. no. 127209

We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking ansatz we can solve exactly the saddle-point equ ations for graphs with uniform connectivity. The resulting ground state ene rgy is in perfect agreement with numerical simulations. For fluctuating con nectivity graphs, the same ansatz can be used in a variational way: For p-s pin models (known as p-XOR-SAT in computer science) it provides the exact c onfigurational entropy together with the dynamical and static critical conn ectivities (for p = 3, gamma (d) = 0.818, and gamma (s) = 0.918), whereas f or hard optimization problems like 3-SAT or Bicoloring it provides new uppe r bounds for their critical thresholds (gamma (var)(c) = 4.396 and gamma (v ar)(c) = 2.149).