TY - GEN
T1 - Conditional random fields, planted constraint satisfaction and entropy concentration
AU - Abbe, Emmanuel
AU - Montanari, Andrea
PY - 2013
Y1 - 2013
N2 - 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 more general structures motivated by coding and community clustering 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 around a deterministic threshold. This implies in particular the concentration of 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.
AB - 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 more general structures motivated by coding and community clustering 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 around a deterministic threshold. This implies in particular the concentration of 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.
KW - Planted models
KW - community clustering
KW - concentration
KW - constraint satisfaction problems
KW - entropy
KW - graphical models
KW - interpolation method
KW - parity-check codes
UR - http://www.scopus.com/inward/record.url?scp=84885219323&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84885219323&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40328-6_24
DO - 10.1007/978-3-642-40328-6_24
M3 - Conference contribution
AN - SCOPUS:84885219323
SN - 9783642403279
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 332
EP - 346
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013
Y2 - 21 August 2013 through 23 August 2013
ER -