ﻻ يوجد ملخص باللغة العربية
We study the problem of reconstructing a perfect matching $M^*$ hidden in a randomly weighted $ntimes n$ bipartite graph. The edge set includes every node pair in $M^*$ and each of the $n(n-1)$ node pairs not in $M^*$ independently with probability $d/n$. The weight of each edge $e$ is independently drawn from the distribution $mathcal{P}$ if $e in M^*$ and from $mathcal{Q}$ if $e otin M^*$. We show that if $sqrt{d} B(mathcal{P},mathcal{Q}) le 1$, where $B(mathcal{P},mathcal{Q})$ stands for the Bhattacharyya coefficient, the reconstruction error (average fraction of misclassified edges) of the maximum likelihood estimator of $M^*$ converges to $0$ as $nto infty$. Conversely, if $sqrt{d} B(mathcal{P},mathcal{Q}) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$ under both the sparse and dense model, resolving the conjecture in [Moharrami et al. 2019, Semerjian et al. 2020]. Furthermore, in the special case of complete exponentially weighted graph with $d=n$, $mathcal{P}=exp(lambda)$, and $mathcal{Q}=exp(1/n)$, for which the sharp threshold simplifies to $lambda=4$, we prove that when $lambda le 4-epsilon$, the optimal reconstruction error is $expleft( - Theta(1/sqrt{epsilon}) right)$, confirming the conjectured infinite-order phase transition in [Semerjian et al. 2020].
This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated random graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the ErdH{o}s-Renyi m
We consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outs
We establish a phase transition known as the all-or-nothing phenomenon for noiseless discrete channels. This class of models includes the Bernoulli group testing model and the planted Gaussian perceptron model. Previously, the existence of the all-or
We present a theory of the multi-threshold second-order phase transition, and experimentally demonstrate the multi-threshold second-order phase transition phenomenon. With carefully selected parameters, in an external cavity diode laser system, we ob
Suppose that $mathcal{P}$ is a property that may be satisfied by a random code $C subset Sigma^n$. For example, for some $p in (0,1)$, $mathcal{P}$ might be the property that there exist three elements of $C$ that lie in some Hamming ball of radius $