Hardness conjecture for the spiked Wishart model
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.