Subexponential optimization and sampling conjecture for the low-temperature CREM

Consider a continuous random energy model (CREM) with concave covariance function AA, inverse temperature β>βc\beta>\beta_c, \tilde\text{ and } ?\text{?}, and ?\text{?}. Let OPT=maxv=NXv\text{OPT}=\text{max}_{|v|=N}X_v and let KL\text{KL} denote Kullback–Leibler divergence. Low-temperature algorithmic tradeoff conjecture. For ?\text{?} and ?\text{?}, there is a 2O~ε(Nα)2^{\widetilde{O}_{\varepsilon}(N^\alpha)}-time algorithm which, with high probability, both finds v^\widehat v satisfying Xv^OPTεN12αX_{\widehat v}\geq\mathrm{OPT}-\varepsilon N^{1-2\alpha} and outputs a distribution μ^\widehat\mu satisfying KL(μ^μβ,N)εN12α\operatorname{KL}(\widehat\mu\|\mu_{\beta,N})\leq\varepsilon N^{1-2\alpha}. The conjecture proposes a Pareto tradeoff between running time and optimization and sampling accuracy in the low-temperature regime, while the supplied text does not specify whether it has been proved or disproved.

Sources & referencesView supporting material

Primary source

Holden Lee and Qiang Wu, “Sampling from the Continuous Random Energy Model in Total Variation Distance”, arXiv:2407.00868 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.