Subexponential optimization and sampling conjecture for the low-temperature CREM
Consider a continuous random energy model (CREM) with concave covariance function , inverse temperature , \tilde\text{ and } , and . Let and let denote Kullback–Leibler divergence. Low-temperature algorithmic tradeoff conjecture. For and , there is a -time algorithm which, with high probability, both finds satisfying and outputs a distribution satisfying . 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.
References
Primary source
Holden Lee and Qiang Wu, “Sampling from the Continuous Random Energy Model in Total Variation Distance”, arXiv:2407.00868 (2025).
Progress summary
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.