Computational hardness conjecture for the spiked Wishart hypothesis test
Computational hardness conjecture for the spiked Wishart hypothesis test
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.
Sources & referencesView supporting material
Primary source
Sohom Bhattacharya and Subhabrata Sen, “Causal inference under interference: computational barriers and algorithmic solutions”, arXiv:2512.08252 (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.