Conditional random fields, planted constraint satisfaction, and entropy concentration

DOI10.4086/TOC.2015.V011A017MaRDI QIDQ3467515zbMATH OpenOpenAlexFDO

Authors Emmanuel Abbe, Andrea Montanari

Publication date 2 February 2016

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2015.v011a017

zbMATH Keywords

clusteringentropygraph-based codesplanted CSPplanted SATstochastic block model

Mathematics Subject Classification ID

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

Recommendations

• Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration
• On the concentration of the number of solutions of random satisfiability formulas
• Reconstruction and clustering in random constraint satisfaction problems
• Models for Random Constraint Satisfaction Problems
• The replica symmetric phase of random constraint satisfaction problems

Cites work

• Candidate one-way functions based on expander graphs
• scientific article; zbMATH DE number 3251924 (Why is no real title available?)
• Tight Bounds for LDPC and LDGM Codes Under MAP Decoding

Cited in

(10)

• Charting the replica symmetric phase
• Optimal testing for planted satisfiability problems
• An information-percolation bound for spin synchronization on general graphs
• Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration
• Community detection and stochastic block models: recent developments
• On the complexity of random satisfiability problems with planted solutions
• Asymptotic mutual information for the balanced binary stochastic block model
• Mutual information for the sparse stochastic block model
• Bad local minima exist in the stochastic block model
• Inference and mutual information on random factor graphs

This page was built for publication: Conditional random fields, planted constraint satisfaction, and entropy concentration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3467515)