The low-degree conjecture for strong detection

About 2 years old · traced to

Let Q\mathcal{Q} and P\mathcal{P} be sufficiently nice distributions, and let Adv⁡≤D(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≥(log⁡n)1+εD\geq (\log n)^{1+\varepsilon}

and that Adv⁡≤D(Q,P)\operatorname{Adv}_{\leq D}(\mathcal{Q},\mathcal{P}) remains bounded as n→∞n\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.

References

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.