Conditional random fields, planted constraint satisfaction and entropy concentration

Emmanuel Abbe, Andrea Montanari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 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 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings
Pages332-346
Number of pages15
DOIs
StatePublished - Oct 15 2013
Event16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013 - Berkeley, CA, United States
Duration: Aug 21 2013Aug 23 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8096 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013
CountryUnited States
CityBerkeley, CA
Period8/21/138/23/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Planted models
  • community clustering
  • concentration
  • constraint satisfaction problems
  • entropy
  • graphical models
  • interpolation method
  • parity-check codes

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

  • Cite this

    Abbe, E., & Montanari, A. (2013). Conditional random fields, planted constraint satisfaction and entropy concentration. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings (pp. 332-346). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8096 LNCS). https://doi.org/10.1007/978-3-642-40328-6_24