5 papers
TP Decoding
Yi Lu, Cyril Measson, Andrea Montanari
`Tree pruning' (TP) is an algorithm for probabilistic inference on binary Markov random fields. It has been recently derived by Dror Weitz and used to construct the first fully pol…
The Generalized Area Theorem and Some of its Consequences
Cyril Measson, Andrea Montanari, Tom Richardson +1
There is a fundamental relationship between belief propagation and maximum a posteriori decoding. The case of transmission over the binary erasure channel was investigated in detai…
Why We Can Not Surpass Capacity: The Matching Condition
Cyril Measson, Andrea Montanari, Rudiger Urbanke
We show that iterative coding systems can not surpass capacity using only quantities which naturally appear in density evolution. Although the result in itself is trivial, the meth…
Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding
Cyril Measson, Andrea Montanari, Ruediger Urbanke
There is a fundamental relationship between belief propagation and maximum a posteriori decoding. A decoding algorithm, which we call the Maxwell decoder, is introduced and provide…
Life Above Threshold: From List Decoding to Area Theorem and MSE
Cyril Measson, Andrea Montanari, Tom Richardson +1
We consider communication over memoryless channels using low-density parity-check code ensembles above the iterative (belief propagation) threshold. What is the computational compl…