Low-degree heuristic for computational detection
Statement
Let and be probability measures for a high-dimensional hypothesis-testing problem based on , with and parameters scaling with . Let be the polynomials on of degree at most , and define the low-degree advantage by
Strong detection means that the sum of type-I and type-II errors tends to zero, while weak detection means that this sum is bounded above by for some fixed . Low-degree heuristic. For natural high-dimensional hypothesis-testing problems, (1) if as , then for some constant no algorithm with running time achieves strong detection; and (2) if as , then for some constant no algorithm with that running time achieves weak detection. This heuristic is a central conditional principle relating low-degree testing bounds to computational hardness, and the source does not establish it as a theorem.
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.