Skip to main content

Conditional random fields, planted constraint satisfaction, and entropy concentration

Author(s): Abbe, Emmanuel; Montanari, A

To refer to this page use:
Abstract: This paper studies a class of probabilistic models on graphs, where edge variables depend on incident node variables through a fixed probability kernel. The class includes planted constraint satisfaction problems (CSPs), as well as other structures motivated by coding theory and community detection problems. It is shown that under mild assumptions on the kernel and for sparse random graphs, the conditional entropy of the node variables given the edge variables concentrates. This implies in particular concentration results for the number of solutions in a broad class of planted CSPs, the existence of a threshold function for the disassortative stochastic block model, and the proof of a conjecture on parity check codes. It also establishes new connections among coding, clustering and satisfiability.
Publication Date:  12
Citation: Abbe, E, Montanari, A. (2015). Conditional random fields, planted constraint satisfaction, and entropy concentration. Theory of Computing, 11 (413 - 443. doi:10.4086/toc.2015.v011a017
DOI: doi:10.4086/toc.2015.v011a017
Pages: 413 - 443
Type of Material: Journal Article
Journal/Proceeding Title: Theory of Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.