Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration

DOI10.1007/978-3-642-40328-6_24zbMath1383.68057arXiv1305.4274OpenAlexW4230202445MaRDI QIDQ2851867

Emmanuel Abbe, Andrea Montanari

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.4274

zbMATH Keywords

entropyinterpolation methodgraphical modelsconstraint satisfaction problemsconcentrationparity-check codescommunity clusteringplanted models

Mathematics Subject Classification ID

Random fields (60G60) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random graphs (graph-theoretic aspects) (05C80) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Measures of information, entropy (94A17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

Isotonic regression with unknown permutations: statistics, computation and adaptation ⋮ Finding one community in a sparse graph ⋮ Asymptotic mutual information for the balanced binary stochastic block model ⋮ Replica bounds by combinatorial interpolation for diluted spin systems

This page was built for publication: Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration