10 problems

Discontinuity conjecture. For any $lambda>1$ and any $t$ with $1leq t<varrho(lambda)$, $t$ is a discontinuity of $F_lambda$ if and only if $t$ is rational.

Degree-profiling conjecture. Replacing the community-recovery algorithm used in this work by the degree-profiling algorithm gives an efficient graph-matching algorithm in the gener…

Computational-threshold conjecture. For random graphs of logarithmic average degree, $\rho^2=\alpha$ is the computational threshold for graph matching.

Computational-threshold conjecture. When $s^2<\alpha$, an information-computation gap exists for correlated Erdős–Rényi graphs.

Exact-matching conjecture. If $G_1\cap G'_2$ has no isolated vertex, then exact graph matching may be possible.

Let $G_1$ and $G_2$ be correlated stochastic block model graphs with community assignment $\boldsymbol{\boldsymbol{\sigma}}$, parameters $\alpha$, $\beta$, and correlation paramete…

Phantom Alignment Strength Conjecture for SGM. Given $n$, $s$, and $\mu'$ as above, there exists $\hat q_{\mathrm{SGM}}=\hat q_{\mathrm{SGM}}(n,s,\mu')\in[0,1]$ with…

Phantom Alignment Strength Conjecture. Subject to the stated caveats, there exists a phantom alignment strength value $\hat q=\hat q(n,s,\mu')\in[0,1]$ such that…

Let $n$ denote the relevant graph size and let $n_c$ denote the number of core vertices whose correspondence is to be recovered. Under the heuristic that the signal from correlatio…

Let $(G_1,G_2)\sim \rho$-SBM$(K,\vec{n},b,\Lambda)$, with $K$ and $\Lambda$ fixed in $n$, and let $\boldsymbol{\sigma}$ be uniformly distributed on $\Pi(n)$. Relative information-l…