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.

Semerjian G., Sicuro G., Zdeborova L. (2020). Recovery thresholds in the sparse planted matching problem. PHYSICAL REVIEW. E, 102(2), 1-18 [10.1103/PhysRevE.102.022304].

Recovery thresholds in the sparse planted matching problem

Sicuro G.;
2020

Abstract

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.
2020
Semerjian G., Sicuro G., Zdeborova L. (2020). Recovery thresholds in the sparse planted matching problem. PHYSICAL REVIEW. E, 102(2), 1-18 [10.1103/PhysRevE.102.022304].
Semerjian G.; Sicuro G.; Zdeborova L.
File in questo prodotto:
File Dimensione Formato  
PhysRevE.102.022304.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per accesso libero gratuito
Dimensione 1.11 MB
Formato Adobe PDF
1.11 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/958320
Citazioni
  • ???jsp.display-item.citation.pmc??? 0
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 4
social impact