Informal low-degree likelihood-ratio conjecture
Statement
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.
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.