Hopkins's low-degree conjecture for hypothesis testing
Statement
Consider asymptotic hypothesis-testing problems between probability measures and . For degree at most , define the low-degree advantage by
Here is the set of real polynomials of degree at most , and denotes total variation distance. An algorithm achieves strong detection if the sum of its type-I and type-II errors tends to zero, and achieves weak detection if that sum is bounded above by for some fixed . Hopkins's low-degree conjecture. For “natural” high-dimensional hypothesis-testing problems between and , the following statements hold: (1) if
as for some satisfying , then there exists a constant such that no algorithm with running time achieves strong detection between and ; and (2) if
under the same total-variation conditions, then there exists a constant such that no algorithm with running time achieves weak detection between and . The conjecture is a proposed bridge from low-degree polynomial analysis to computational lower bounds for natural high-dimensional testing problems. The source does not provide evidence resolving it in full generality.
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.