3 problems

The NFM strong-node containment conjecture for ℓ₂-norm-diag
arXiv@arxiv
NFM strong-node containment conjecture. With probability not converging to $0$ as $n\to\infty$ , $\ell_2$ -norm-diag returns exactly $k$ disjoint clusters $V_1',\dots,V_k'$ such that…
Conjectureopencommunity-detection correlation-clustering robust-optimization
1
The NFM positive-semidefinite subgraph conjecture under Dirichlet noise
arXiv@arxiv
NFM positive-semidefinite subgraph conjecture. There exists a scalar $t(k,\bm{\alpha})\in(0.5,1/\sqrt{2})$ such that, for every $j\in[k]$ , $G[V_j']$ satisfies the hypothesis of The…
Conjectureopencorrelation-clustering spectral-graph-theory stochastic-models
0
The NFM exact-recovery impossibility conjecture under Dirichlet noise
arXiv@arxiv
NFM exact-recovery impossibility conjecture. No algorithm can exactly recover the true clusters in $G$ with probability not converging to $0$ as $n\to\infty$ .
Conjectureopencommunity-detection correlation-clustering stochastic-models
1

The NFM strong-node containment conjecture for ℓ₂-norm-diag