Conditional random fields, planted constraint satisfaction, and entropy concentration

Emmanuel Abbe, Andrea Montanari

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)413-443
Number of pages31
JournalTheory of Computing
Volume11
DOIs
StatePublished - Dec 29 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Clustering
  • Entropy
  • Graph-based codes
  • Planted CPS
  • Planted SAT
  • Stochastic block model

Fingerprint Dive into the research topics of 'Conditional random fields, planted constraint satisfaction, and entropy concentration'. Together they form a unique fingerprint.

Cite this