Conditional Random Fields, Planted Constraint Satisfaction, and Entropy\n Concentration

2013/05/18 by Emmanuel Abbé, Andrea Montanari, Abbe, Emmanuel +1 · 1 citation
Economics, Econometrics and Finance · #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Information Theory (cs.IT) #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1305.4274

openalex publication_date 2013/05/18 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28

Abstract

This paper studies a class of probabilistic models on graphs, where edge\nvariables depend on incident node variables through a fixed probability kernel.\nThe class includes planted con- straint satisfaction problems (CSPs), as well\nas more general structures motivated by coding and community clustering\nproblems. It is shown that under mild assumptions on the kernel and for sparse\nrandom graphs, the conditional entropy of the node variables given the edge\nvariables concentrates around a deterministic threshold. This implies in\nparticular the concentration of the number of solutions in a broad class of\nplanted CSPs, the existence of a threshold function for the disassortative\nstochastic block model, and the proof of a conjecture on parity check codes. It\nalso establishes new connections among coding, clustering and satisfiability.\n

Cited by

• Non-asymptotic goodness-of-fit tests and model selection in valued stochastic blockmodels

Related

• A Proof Of The Block Model Threshold Conjecture
• Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Certifying solution geometry in random CSPs: counts, clusters and balance
• Does robustness imply tractability? A lower bound for planted clique in the semi-random model