The planted matching problem: sharp threshold and infinite-order phase transition
The planted matching problem: sharp threshold and infinite-order phase transition
复制标题
种植匹配问题：尖锐阈值和无限阶相变
DOI：
10.1007/s00440-023-01208-6
复制
发表时间：
2023
影响因子：
2
通讯作者：
Yang, Dana
中科院分区：
文献类型：
--
作者：
Ding, Jian;Wu, Yihong;Xu, Jiaming;Yang, Dana
We study the problem of reconstructing a perfect matchinghidden in a randomly weightedbipartite graph. The edge set includes every node pair inand each of thenode pairs not inindependently with probabilityd/n. The weight of each edgeeis independently drawn from the distributionifand fromif. We show that if, wherestands for the Bhattacharyya coefficient, the reconstruction error (average fraction of misclassified edges) of the maximum likelihood estimator ofconverges to 0 as. Conversely, iffor an arbitrarily small constant, the reconstruction error for any estimator is shown to be bounded away from 0 for both the sparse (fixedd) and dense (growingd) regimes, resolving the conjecture in Moharrami et al. (Ann Appl Probab 31(6):2663–2720, 2021. https://doi.org/10.1214/20-AAP1660) and Semerjian et al. (Phys Rev E 102:022304, 2020. https://doi.org/10.1103/PhysRevE.102.022304). Furthermore, in the special case of complete exponentially weighted graph with,, and, for which the sharp threshold simplifies to, we prove that when, the optimal reconstruction error is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exp \left( - \varTheta (1/\sqrt{\epsilon }) \right) $$\end{document}, confirming the conjectured infinite-order phase transition in Semerjian et al. (2020).
We study the problem of reconstructing a perfect matchinghidden in a randomly weightedbipartite graph. The edge set includes every node pair inand each of thenode pairs not inindependently with probabilityd/n. The weight of each edgeeis independently drawn from the distributionifand fromif. We show that if, wherestands for the Bhattacharyya coefficient, the reconstruction error (average fraction of misclassified edges) of the maximum likelihood estimator ofconverges to 0 as. Conversely, iffor an arbitrarily small constant, the reconstruction error for any estimator is shown to be bounded away from 0 for both the sparse (fixedd) and dense (growingd) regimes, resolving the conjecture in Moharrami et al. (Ann Appl Probab 31(6):2663–2720, 2021. https://doi.org/10.1214/20-AAP1660) and Semerjian et al. (Phys Rev E 102:022304, 2020. https://doi.org/10.1103/PhysRevE.102.022304). Furthermore, in the special case of complete exponentially weighted graph with,, and, for which the sharp threshold simplifies to, we prove that when, the optimal reconstruction error is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exp \left( - \varTheta (1/\sqrt{\epsilon }) \right) $$\end{document}, confirming the conjectured infinite-order phase transition in Semerjian et al. (2020).
登录
查看更多内容
Parisi关于随机分配问题猜想的证明
影响因子：
2
作者：
Svante Linusson;Johan Wästlund
通讯作者：
Johan Wästlund
Parisi 和 Coppersmith-Sorkin 随机分配猜想的证明
影响因子：
1
作者：
Chandra Nair;B. Prabhakar;Mayank Sharma
通讯作者：
Mayank Sharma
种植结构的统计问题：信息理论和计算限制
DOI：
--
发表时间：
2018
期刊：
Information-Theoretic Methods in Data Science
影响因子：
--
作者：
Yihong Wu;Jiaming Xu
通讯作者：
Jiaming Xu
DOI：
10.1137/1.9781611977073.36
发表时间：
2021-07
期刊：
ArXiv
影响因子：
--
作者：
Dmitriy Kunisky;Jonathan Niles-Weed
通讯作者：
Dmitriy Kunisky;Jonathan Niles-Weed
稀疏种植匹配问题中的恢复阈值
DOI：
10.1103/physreve.102.022304
发表时间：
2020
期刊：
Physical review. E
影响因子：
--
作者：
G. Semerjian;G. Sicuro;Lenka Zdeborov'a
通讯作者：
Lenka Zdeborov'a