Optimal list decoding from noisy entropy inequality

12/02/2022

∙

by   Jan Hązła, et al.

∙

0

∙

share

A noisy entropy inequality for boolean functions by Samorodnitsky is applied to binary codes. It is shown that a binary code that achieves capacity on the binary erasure channel admits optimal list size for list decoding on some binary symmetric channels (in a regime where this optimal list size is exponentially large).