ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let P\mathbb P and Q\mathbb Q be probability measures for a high-dimensional hypothesis-testing problem based on Y∈RN\mathsf Y\in\mathbb R^N, with N=NnN=N_n and parameters scaling with nn. Let PD\mathcal P_D be the polynomials on RNn\mathbb R^{N_n} of degree at most DD, and define the low-degree advantage by

Adv≤D(P;Q):=sup⁡f∈PD{EP[f]EQ[f2]}.\mathsf{Adv}_{\leq D}(\mathbb P;\mathbb Q):=\sup_{f\in\mathcal P_D}\left\{\frac{\mathbb E_{\mathbb P}[f]}{\sqrt{\mathbb E_{\mathbb Q}[f^2]}}\right\}.

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 1−ϵ1-\epsilon for some fixed ϵ>0\epsilon>0. Low-degree heuristic. For natural high-dimensional hypothesis-testing problems, (1) if Adv≤D(P;Q)=O(1)\mathsf{Adv}_{\leq D}(\mathbb P;\mathbb Q)=O(1) as n→∞n\to\infty, then for some constant CC no algorithm with running time ND/(Clog⁡N)N^{D/(C\log N)} achieves strong detection; and (2) if Adv≤D(P;Q)=1+o(1)\mathsf{Adv}_{\leq D}(\mathbb P;\mathbb Q)=1+o(1) as n→∞n\to\infty, then for some constant CC 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.