Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe planted matching problem: Sharp threshold and infinite-order phase transition
59
0
0.0
(
0
)
Added by
Dana Yang
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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].
rate research
Read More
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 model where the two graphs are subsampled from a common parent ErdH{o}s-Renyi graph $mathcal{G}(n,p)$. For dense graphs with $p=n^{-o(1)}$, we prove that there exists a sharp threshold, above which one can correctly match all but a vanishing fraction of vertices and below which correctly matching any positive fraction is impossible, a phenomenon known as the all-or-nothing phase transition. Even more strikingly, in the Gaussian setting, above the threshold all vertices can be exactly matched with high probability. In contrast, for sparse ErdH{o}s-Renyi graphs with $p=n^{-Theta(1)}$, we show that the all-or-nothing phenomenon no longer holds and we determine the thresholds up to a constant factor. Along the way, we also derive the sharp threshold for exact recovery, sharpening the existing results in ErdH{o}s-Renyi graphs. The proof of the negative results builds upon a tight characterization of the mutual information based on the truncated second-moment computation and an area theorem that relates the mutual information to the integral of the reconstruction error. The positive results follows from a tight analysis of the maximum likelihood estimator that takes into account the cycle structure of the induced permutation on the edges.
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 outside the planted matching. A recent work has demonstrated the existence of a phase transition, in the large size limit, between a full and a partial recovery phase for a specific form of the weights distribution on fully connected graphs. We generalize and extend this result in two directions: we obtain a criterion for the location of the phase transition for generic weights distributions and possibly sparse graphs, exploiting a technical connection with branching random walk processes, as well as a quantitatively more precise description of the critical regime around the phase transition.
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-nothing phenomenon for such models was only known in a limited range of parameters. Our work extends the results to all signals with arbitrary sublinear sparsity. Over the past several years, the all-or-nothing phenomenon has been established in various models as an outcome of two seemingly disjoint results: one positive result establishing the all half of all-or-nothing, and one impossibility result establishing the nothing half. Our main technique in the present work is to show that for noiseless discrete channels, the all half implies the nothing half, that is a proof of all can be turned into a proof of nothing. Since the all half can often be proven by straightforward means -- for instance, by the first-moment method -- our equivalence gives a powerful and general approach towards establishing the existence of this phenomenon in other contexts.
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 observe second-order phase transition with multiple (three or four) thresholds in the measured power-current-temperature three dimensional phase diagram. Such controlled death and revival of second-order phase transition sheds new insight into the nature of ubiquitous second-order phase transition. Our theory and experiment show that the single threshold second-order phase transition is only a special case of the more general multi-threshold second-order phase transition, which is an even richer phenomenon.
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 $pn$. We say that $R^*$ is the threshold rate for $mathcal{P}$ if a random code of rate $R^{*} + varepsilon$ is very likely to satisfy $mathcal{P}$, while a random code of rate $R^{*} - varepsilon$ is very unlikely to satisfy $mathcal{P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably symmetric. For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property $mathcal{P}$ above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
