Unsolved
From low-degree hardness to unconditional polynomial-time hardness
Sourced from the work of Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li
§ Problem Statement
§ Discussion
Loading discussion…
§ Significance & Implications
§ Known Partial Results
§ References
[1]
A Computational Transition for Detecting Correlated Stochastic Block Models by Low-Degree Polynomials
Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li (2024)
Annals of Statistics (to appear)
📍 Section 1 (Introduction), Theorem 1.3 (informal), item (2) with the adjacent “lack of complexity-theoretic tools” discussion (lines introducing the gap to polynomial-time hardness), p. 3
Source paper where this problem appears.