ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.