The planted k-factor problem

DOI10.1088/1751-8121/ABEE9DMaRDI QIDQ5877084zbMATH OpenOpenAlexFDO

Authors Gabriele Sicuro, Lenka Zdeborová

Publication date 3 February 2023

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2010.13700

zbMATH Keywords

belief propagationcavity methoddisordered systemsgraph theoryinferenceplanting

Mathematics Subject Classification ID

Quantum theory (81-XX) Statistical mechanics, structure of matter (82-XX)

Recommendations

• The planted matching problem: phase transitions and exact results
• Reconstruction and estimation in the planted partition model
• A new approach to the planted clique problem
• Finding Planted Partitions in Random Graphs with General Degree Distributions

Cites work

• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Chernoff's theorem in the branching random walk
• Exact Recovery in the Stochastic Block Model
• Front propagation into unstable states: Universal algebraic convergence towards uniformly translating pulled fronts
• Group testing with random pools: Phase transitions and optimal strategy
• Hidden Hamiltonian cycle recovery via linear programming
• Information, Physics, and Computation
• Matchings on infinite graphs
• Modern Coding Theory
• Random graphs.
• The first birth problem for an age-dependent branching process
• Uniform generation of random regular graphs

Cited in

(2)

• The planted matching problem: sharp threshold and infinite-order phase transition
• The planted k-factor problem

This page was built for publication: The planted k-factor problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5877084)