Key points are not available for this paper at this time.
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 equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p0ex{0ex}=0ex{0ex}3, ₃0ex{0ex}=0ex{0ex}0. 818, and ₒ0ex{0ex}=0ex{0ex}0. 918), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds (₂^var0ex{0ex}=0ex{0ex}4. 396 and ₂^var0ex{0ex}=0ex{0ex}2. 149).
Franz et al. (Fri,) studied this question.