Hardness conjecture for the spiked Wishart model

At least 2 years old · documented by

Let β∈[−1,∞)\beta \in [-1,\infty) and γ>0\gamma>0. For each n∈Nn\in\mathbb N, set N=⌈n/γ⌉N=\lceil n/\gamma\rceil, and let P\mathbb P and Q\mathbb Q be the spiked Wishart distributions defined by the null model Q\mathbb Q with independent samples yi∼N(0,In)\bm y_i\sim\mathcal N(\bm 0,\bm I_n) and the planted model P\mathbb P obtained by sampling x∼Unif⁡({±1}n)\bm x\sim\operatorname{Unif}(\{\pm1\}^n) and then independently sampling yi∼N(0,In+(β/n)xx⊤)\bm y_i\sim\mathcal N(\bm 0,\bm I_n+(\beta/n)\bm x\bm x^{\top}). Write this sequence of distribution pairs as Wishart(β,γ)\mathsf{Wishart}(\beta,\gamma). Hardness of the Wishart model. If β>−1\beta>-1 and β2<γ\beta^2<\gamma, there is no polynomial-time hypothesis test between the distributions of Wishart(β,γ)\mathsf{Wishart}(\beta,\gamma): no randomized algorithm f:(Rn)N→{p,q}f:(\mathbb R^n)^N\to\{\mathtt p,\mathtt q\} running in polynomial time in nn satisfies

lim⁡n→∞P[f(y1,…,yN)=p]=lim⁡n→∞Q[f(y1,…,yN)=q]=1.\lim_{n\to\infty}\mathbb P[f(\bm y_1,\dots,\bm y_N)=\mathtt p]=\lim_{n\to\infty}\mathbb Q[f(\bm y_1,\dots,\bm y_N)=\mathtt q]=1.

This conjecture is the key computational-hardness assumption used to obtain evidence that the constant 11 in spectral conditions for general-purpose Ising-model sampling and free-energy approximation is optimal; its status is not resolved in the source.

References

Primary source

Dmitriy Kunisky, “Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation”, arXiv:2307.12581 (2023).

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.