Informal low-degree likelihood-ratio conjecture
Let and be probability distributions on , with likelihood ratio . For a degree bound , let denote the orthogonal projection of onto the degree- polynomials under the inner product.
Informal low-degree conjecture. For “nice” distributions and , if
for some , then there is no randomized polynomial-time algorithm for strong detection between and .
The conjecture formalizes the heuristic that bounded low-degree likelihood-ratio norm rules out efficient strong detection. It is explicitly informal because the paper does not define “nice” distributions; precise variants use coordinate degree. Evidence and applications are discussed for models including the stochastic block model and spiked tensor model, while the converse is not expected to hold.
References
- Afonso S. Bandeira, Dmitriy Kunisky and Alexander S. Wein, “Computational Hardness of Certifying Bounds on Constrained PCA Problems”, arXiv:1902.07324 (2019).
Progress summary
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.