Computational hardness conjecture for the spiked Wishart hypothesis test

About 1 year old · traced to

Let β≥−1\beta\geq -1 and γ>0\gamma>0, and for n∈Nn\in\mathbb{N} set N=⌈n/γ⌉N=\lceil n/\gamma\rceil. Under μ0\mu_0, draw z1,…,zN∼N(0,In)\mathbf{z}_1,\ldots,\mathbf{z}_N\sim N(0,I_n) independently. Under μ1\mu_1, first draw u∼U({±1}n)\mathbf{u}\sim\mathrm{U}(\{\pm1\}^n), then, conditional on u\mathbf{u}, draw z1,…,zN∼N(0,In+(β/n)uu⊤)\mathbf{z}_1,\ldots,\mathbf{z}_N\sim\mathsf{N}(0,I_n+(\beta/n)\mathbf{u}\mathbf{u}^{\top}). Denote these two distributions collectively by Wishart(β,γ)\mathrm{Wishart}(\beta,\gamma). A polynomial-time hypothesis test is a two-valued function of (z1,…,zN)(\mathbf{z}_1,\ldots,\mathbf{z}_N) evaluable in polynomial time in nn, and it is asymptotically consistent if its probabilities of correctly identifying μ0\mu_0 and μ1\mu_1 both tend to 11. Computational hardness conjecture for the spiked Wishart hypothesis test. If β>−1\beta>-1 and β2<γ\beta^2<\gamma, there does not exist an asymptotically consistent sequence of polynomial-time hypothesis tests between the distributions of Wishart(β,γ)\mathrm{Wishart}(\beta,\gamma). 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.

References

Primary source

Sohom Bhattacharya and Subhabrata Sen, “Causal inference under interference: computational barriers and algorithmic solutions”, arXiv:2512.08252 (2025).

Progress summary

Never refreshed

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.