Hardness conjecture for the spiked Wishart model
Hardness conjecture for the spiked Wishart model
Let and . For each , set , and let and be the spiked Wishart distributions defined by the null model with independent samples and the planted model obtained by sampling and then independently sampling . Write this sequence of distribution pairs as . Hardness of the Wishart model. If and , there is no polynomial-time hypothesis test between the distributions of : no randomized algorithm running in polynomial time in satisfies
This conjecture is the key computational-hardness assumption used to obtain evidence that the constant in spectral conditions for general-purpose Ising-model sampling and free-energy approximation is optimal; its status is not resolved in the source.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Dmitriy Kunisky, “Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation”, arXiv:2307.12581 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.