The algorithmic hardness threshold for continuous random energy models (Q2176074)

Summary: We prove an algorithmic hardness result for finding low-energy states in the so-called \textit{continuous random energy model (CREM)}, introduced by \textit{A. Bovier} and \textit{I. Kurkova} in [Ann. Inst. Henri Poincaré, Probab. Stat. 40, No. 4, 439--480 (2004; Zbl 1121.82020); ibid. 40, No. 4, 481--495 (2004; Zbl 1121.82021)] as an extension of Derrida's \textit{generalized random energy model}. The CREM is a model of a random energy landscape \((X_v)_{v \in \{0,1\}^N}\) on the discrete hypercube with built-in hierarchical structure, and can be regarded as a toy model for strongly correlated random energy landscapes such as the family of \(p\)-spin models including the Sherrington-Kirkpatrick model. The CREM is parameterized by an increasing function \(A \colon [0, 1]\to[0, 1]\), which encodes the correlations between states. We exhibit an \textit{algorithmic hardness threshold} \(x_\ast\), which is explicit in terms of \(A\). More precisely, we obtain two results: First, we show that a renormalization procedure combined with a greedy search yields for any \(\varepsilon > 0\) a linear-time algorithm which finds states \(v \in \{0,1\}^N\) with \(X_v \ge (x_\ast-\varepsilon) N\). Second, we show that the value \(x_\ast\) is essentially best-possible: for any \(\varepsilon > 0\), any algorithm which finds states \(v\) with \(X_v \ge (x_\ast+\varepsilon)N\) requires exponentially many queries in expectation and with high probability. We further discuss what insights this study yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.