2023/12/07 by Emmanuel Abbé, Abbe, Emmanuel, Colin Sandon +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2312.04329
openalex publication_date 2023/12/07 · openalex created_date 2023/12/09 · openalex updated_date 2026/07/28
This paper shows that a class of codes such as Reed-Muller (RM) codes have vanishing bit-error probability below capacity on symmetric channels. The proof relies on the notion of `camellia codes': a class of symmetric codes decomposable into `camellias', i.e., set systems that differ from sunflowers by allowing for scattered petal overlaps. The proof then follows from a boosting argument on the camellia petals with second moment Fourier analysis. For erasure channels, this gives a self-contained proof of the bit-error result in Kudekar et al.'17, without relying on sharp thresholds for monotone properties Friedgut-Kalai'96. For error channels, this gives a shortened proof of Reeves-Pfister'23 with an exponentially tighter bound, and a proof variant of the bit-error result in Abbe-Sandon'23. The control of the full (block) error probability still requires Abbe-Sandon'23 for RM codes.