pdf icon
Volume 11 (2015) Article 17 pp. 413-443
APPROX-RANDOM 2013 Special Issue
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration
Received: October 27, 2013
Revised: November 30, 2014
Published: December 29, 2015
Download article from ToC site:
[PDF (335K)] [PS (1927K)] [Source ZIP]
Keywords: planted SAT, planted CSP, clustering, stochastic block model, graph-based codes, entropy
ACM Classification: G.3, H.1.1, G.2.2
AMS Classification: 68Q87, 68P30, 05C80

Abstract: [Plain Text Version]

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.

A preliminary version of this paper appeared in the Proc. of RANDOM, Berkeley, 2013.