Subexponential optimization and sampling conjecture for the low-temperature CREM
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.