2 problems

0 votes0 replies0 views
The polynomial-time hardness conjecture for distinguishing the alternative planted distribution
Let $\mathcal{Q}=G(n,q)$ be the null distribution, and let $\widetilde{\mathcal{P}}$ be a different planted distribution that contains a dense subgraph with high probability. The r…
Conjectureopencomputational-complexity dense-subgraph low-degree-methodsarXiv posted 2 days ago
0 votes0 replies0 views
The SoS–low-degree relationship conjecture for dense subgraph detection
The paper studies two kinds of computational evidence for dense subgraph detection: failure of the sum-of-squares (SoS) hierarchy and failure of low-degree polynomial tests. SoS–lo…
Conjectureopendense-subgraph low-degree-methods sum-of-squaresarXiv posted 2 days ago

The polynomial-time hardness conjecture for distinguishing the alternative planted distribution