The low-degree conjecture for strong detection
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.