2 problems

0 votes0 replies0 views
Polynomial-time hardness conjecture for the hard phase of the spiked Wigner model
Consider the spiked Wigner model with the two-point prior … where $p\in(0,1)$ , and let $\lambda_c$ be the information-theoretic threshold. In the region $\lambda_c<\lambda<1$ , non-…
Conjectureopencomputational-complexity spiked-wigner statistical-inferencearXiv posted 2 days ago
0 votes0 replies0 views
The refined low-degree conjecture for spiked Wigner testing
Refined low-degree conjecture. Fix $0<\delta_1<\delta_2$ . Every sequence $f=f_n$ computable in time $\exp(O(n^{\delta_1}))$ satisfies
Conjectureopencomputational-statistics low-degree-method spiked-wignerarXiv posted 2 days ago

Polynomial-time hardness conjecture for the hard phase of the spiked Wigner model