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.
References
Primary source
Dmitriy Kunisky, “Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation”, arXiv:2307.12581 (2023).
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.