The planted k-factor problem

Gabriele Sicuro; Lenka Zdeborova

doi:10.1088/1751-8121/abee9d

The planted k-factor problem

Gabriele Sicuro, Lenka Zdeborova

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

60 Downloads (Pure)

Abstract

We consider the problem of recovering an unknown k-factor, hidden in a weighted random graph. For k = 1 this is the planted matching problem, while the k = 2 case is closely related to the planted traveling salesman problem. The inference problem is solved by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted sub-graph. We argue that, in the large size limit, a phase transition can appear between a full and a partial recovery phase as function of the signal-to-noise ratio. We give a criterion for the location of the transition.

Original language	English
Article number	175002
Journal	Journal of Physics A: Mathematical and Theoretical
Volume	54
Issue number	17
DOIs	https://doi.org/10.1088/1751-8121/abee9d
Publication status	Published - 30 Apr 2021

Access to Document

10.1088/1751-8121/abee9d

The planted k-factor_SICURO_Accepted 15 Mar 21_GOLD_VoRFinal published version, 1.5 MBLicence: CC BY

Cite this

@article{bbd7f16005ce48a788e1acdccf5904d9,

title = "The planted k-factor problem",

abstract = "We consider the problem of recovering an unknown k-factor, hidden in a weighted random graph. For k = 1 this is the planted matching problem, while the k = 2 case is closely related to the planted traveling salesman problem. The inference problem is solved by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted sub-graph. We argue that, in the large size limit, a phase transition can appear between a full and a partial recovery phase as function of the signal-to-noise ratio. We give a criterion for the location of the transition.",

author = "Gabriele Sicuro and Lenka Zdeborova",

note = "Funding Information: The authors acknowledge collaboration with Guilhem Semerjian on the work [8] that was the source of the key theoretical ideas underlying the analysis in the present paper and for many insightful discussions on the problem. This project has received funding from the European Union's Horizon 2020 research and innovation program under the Marie Sk?odowska-Curie Grant agreement CoSP No. 823748, and from the French Agence Nationale de la Recherche under Grant ANR-17-CE23-0023-01 PAIL. Publisher Copyright: {\textcopyright} 2021 The Author(s). Published by IOP Publishing Ltd.",

year = "2021",

month = apr,

day = "30",

doi = "10.1088/1751-8121/abee9d",

language = "English",

volume = "54",

journal = "Journal of Physics A: Mathematical and Theoretical",

issn = "1751-8113",

publisher = "IOP Publishing",

number = "17",

}

TY - JOUR

T1 - The planted k-factor problem

AU - Sicuro, Gabriele

AU - Zdeborova, Lenka

N1 - Funding Information: The authors acknowledge collaboration with Guilhem Semerjian on the work [8] that was the source of the key theoretical ideas underlying the analysis in the present paper and for many insightful discussions on the problem. This project has received funding from the European Union's Horizon 2020 research and innovation program under the Marie Sk?odowska-Curie Grant agreement CoSP No. 823748, and from the French Agence Nationale de la Recherche under Grant ANR-17-CE23-0023-01 PAIL. Publisher Copyright: © 2021 The Author(s). Published by IOP Publishing Ltd.

PY - 2021/4/30

Y1 - 2021/4/30

N2 - We consider the problem of recovering an unknown k-factor, hidden in a weighted random graph. For k = 1 this is the planted matching problem, while the k = 2 case is closely related to the planted traveling salesman problem. The inference problem is solved by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted sub-graph. We argue that, in the large size limit, a phase transition can appear between a full and a partial recovery phase as function of the signal-to-noise ratio. We give a criterion for the location of the transition.

AB - We consider the problem of recovering an unknown k-factor, hidden in a weighted random graph. For k = 1 this is the planted matching problem, while the k = 2 case is closely related to the planted traveling salesman problem. The inference problem is solved by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted sub-graph. We argue that, in the large size limit, a phase transition can appear between a full and a partial recovery phase as function of the signal-to-noise ratio. We give a criterion for the location of the transition.

UR - http://www.scopus.com/inward/record.url?scp=85104577046&partnerID=8YFLogxK

U2 - 10.1088/1751-8121/abee9d

DO - 10.1088/1751-8121/abee9d

M3 - Article

SN - 1751-8113

VL - 54

JO - Journal of Physics A: Mathematical and Theoretical

JF - Journal of Physics A: Mathematical and Theoretical

IS - 17

M1 - 175002

ER -

The planted k-factor problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this