10 problems

Feasibility conjecture. Partial alignment is feasible: there exists an estimator $\hat{\boldsymbol{\pi}}$ and some $\varepsilon>0$ such that, with high probability,

Let $L^{(d)}$ be the score in the infinite-alphabet model and let $\widehat{L}^{(d)}$ be its finite-$m$ version. Write $\widehat{s}_{\rm algo}(\lambda)$ for the transition line of…

Let two correlated Erdős–Rényi graphs on $n$ vertices have edge correlation coefficient $\rho_\mathrm{u}$. Exact recovery means finding the vertex correspondence between the graphs…

Positive limiting threshold conjecture. The critical value remains strictly positive at large average degree:

Let $s<1$ be the non-isomorphic case, let $\mathcal{C}^*$ denote the largest subset of nodes that one can hope to align in the sparse regime, and let $\mathcal{I}$ be the set of in…

Fix parameters $(\lambda,s)$ in the correlated Erdős–Rényi model $\mathcal{G}(n,\lambda/n,s)$. One-sided correlation detection in trees is said to fail when none of the equivalent…

Consider the graph alignment problem and its associated tree correlation detection problem. Graph alignment is called feasible in polynomial time if a polynomial-time algorithm can…

Partial reconstruction threshold conjecture. If $\lambda s \leq 1$, then partial reconstruction is impossible: for every $\alpha>0$ and every estimator $\hat{\pi}$,

Consider graph database alignment with correlation parameter $\rho$, where exact recovery has threshold … Almost exact recovery means finding an estimator that coincides with the p…

Let $\lambda$ be the average degree, let $s$ be the correlation parameter, let $\delta$ be the parameter appearing in the rate $\gamma(\lambda,s,\delta)$, and let $\gamma(\lambda)$…