The low-degree conjecture for strong detection

Let Q\mathcal{Q} and P\mathcal{P} be sufficiently nice distributions, and let AdvD(Q,P)\operatorname{Adv}_{\leq D}(\mathcal{Q},\mathcal{P}) denote the degree-DD low-degree advantage for distinguishing them. Suppose that there exists ε>0\varepsilon>0 and D=D(n)D=D(n) satisfying

D(logn)1+εD\geq (\log n)^{1+\varepsilon}

and that AdvD(Q,P)\operatorname{Adv}_{\leq D}(\mathcal{Q},\mathcal{P}) remains bounded as nn\to\infty. Low-degree conjecture. There is no polynomial-time algorithm that achieves strong detection between Q\mathcal{Q} and P\mathcal{P}. This is an informal version of the low-degree conjecture attributed to Hopkins. It proposes that bounded low-degree advantage at sufficiently high degree rules out efficient strong detection, under the unspecified regularity condition that the distributions are sufficiently nice.

Sources & referencesView supporting material

Primary source

Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein and Xifan Yu, “Statistical inference of a ranked community in a directed graph”, arXiv:2411.19885 (2024).

Progress summary

Never refreshed

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.