Computational hardness conjecture for the spiked Wishart hypothesis test

Let β1\beta\geq -1 and γ>0\gamma>0, and for nNn\in\mathbb{N} set N=n/γN=\lceil n/\gamma\rceil. Under μ0\mu_0, draw z1,,zNN(0,In)\mathbf{z}_1,\ldots,\mathbf{z}_N\sim N(0,I_n) independently. Under μ1\mu_1, first draw uU({±1}n)\mathbf{u}\sim\mathrm{U}(\{\pm1\}^n), then, conditional on u\mathbf{u}, draw z1,,zNN(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.

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

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.