The mutual information of a class of graphical channels

Emmanuel Auguste Abbe, Andrea Montanari

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

2 Scopus citations

Abstract

This paper studies a class of channels obtained by combining a graph and a memoryless channel. A particular example is a memoryless channel pre-coded with a graph-based codes. Other examples are planted constrained satisfaction problems, and probabilistic network models with communities. In an earlier work by the authors, concentration results are obtained for such channels when the graphs is a sparse Erdos-Renyi graph. We overview in this note the approach in an information-theoretic framework, describe how it establishes a conjecture on parity-check codes, and connect the coding and community detection problems.

Original languageEnglish (US)
Title of host publication2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
PublisherIEEE Computer Society
Pages20-25
Number of pages6
ISBN (Print)9781479934096
DOIs
StatePublished - Jan 1 2013
Event51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 - Monticello, IL, United States
Duration: Oct 2 2013Oct 4 2013

Publication series

Name2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013

Other

Other51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
CountryUnited States
CityMonticello, IL
Period10/2/1310/4/13

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering

Cite this