Sharp thresholds in inference of planted subgraphs

DOI10.1214/24-AAP2120MaRDI QIDQ6974240zbMATH OpenFDO

Authors Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, Ilias Zadik

Publication date 10 June 2025

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/24-AAP2120

zbMATH Keywords

all-or-nothing transitionKahn-Kalai expectation thresholdplanted subgraph model

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Bayesian inference (62F15) Nonparametric inference (62G99)

Cites work

• A nearly tight sum-of-squares lower bound for the planted clique problem
• A proof of the Kahn–Kalai conjecture
• A structure theorem for Boolean functions with small total influences
• Are many small sets explicitly small?
• Boolean functions with low average sensitivity depend on few coordinates
• Coding for Sunflowers
• Community detection in dense random networks
• Estimation in Gaussian Noise: Properties of the Minimum Mean-Square Error
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Hamiltonian circuits in random graphs
• Hidden Hamiltonian cycle recovery via linear programming
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 5504150 (Why is no real title available?)
• scientific article; zbMATH DE number 17684 (Why is no real title available?)
• Improved bounds for the sunflower lemma
• Information theoretic limits of learning a sparse rule
• It was ``all for ``nothing: sharp phase transitions for noiseless discrete channels
• Large Cliques Elude the Metropolis Process
• Note on sunflowers
• Optimal errors and phase transitions in high-dimensional generalized linear models
• Reed-Muller codes achieve capacity on erasure channels
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Sharp thresholds of graph properties, and the k-sat problem
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• Statistical algorithms and a lower bound for detecting planted cliques
• Statistical Physics of Spin Glasses and Information Processing
• Strongly balanced graphs and random graphs
• The all-or-nothing phenomenon in sparse linear regression
• The planted matching problem: phase transitions and exact results
• The planted matching problem: sharp threshold and infinite-order phase transition
• The Replica-Symmetric Prediction for Random Linear Estimation With Gaussian Matrices Is Exact
• Threshold functions for small subgraphs
• Thresholds and Expectation Thresholds
• Thresholds versus fractional expectation-thresholds

This page was built for publication: Sharp thresholds in inference of planted subgraphs

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