scientific article

DOI10.4086/toc.2015.v011a017zbMath1351.68190OpenAlexW2963383801MaRDI QIDQ3467515

Emmanuel Abbe, Andrea Montanari

Publication date: 2 February 2016

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

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

entropyclusteringstochastic block modelgraph-based codesplanted CSPplanted SAT

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 (8)

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Information-theoretic thresholds from the cavity method ⋮ An information-percolation bound for spin synchronization on general graphs ⋮ Mutual information for the sparse stochastic block model ⋮ Asymptotic mutual information for the balanced binary stochastic block model ⋮ Charting the replica symmetric phase ⋮ Community Detection and Stochastic Block Models ⋮ Optimal testing for planted satisfiability problems

Cites Work

• Unnamed Item
• Candidate One-Way Functions Based on Expander Graphs
• Tight Bounds for LDPC and LDGM Codes Under MAP Decoding

This page was built for publication: