The low-degree conjecture for strong detection
Let and be sufficiently nice distributions, and let denote the degree- low-degree advantage for distinguishing them. Suppose that there exists and satisfying
and that remains bounded as . Low-degree conjecture. There is no polynomial-time algorithm that achieves strong detection between and . 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
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.