Computational hardness conjecture for the spiked Wishart hypothesis test
Statement
Let and , and for set . Under , draw independently. Under , first draw , then, conditional on , draw . Denote these two distributions collectively by . A polynomial-time hypothesis test is a two-valued function of evaluable in polynomial time in , and it is asymptotically consistent if its probabilities of correctly identifying and both tend to . Computational hardness conjecture for the spiked Wishart hypothesis test. If and , there does not exist an asymptotically consistent sequence of polynomial-time hypothesis tests between the distributions of . This conjecture posits an average-case computational barrier for distinguishing the null Wishart model from the planted rank-one spiked model in the stated parameter regime; the parser supplies no evidence that it has been resolved.
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.