← All problems

The low-degree conjecture for strong detection

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
  1. 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.