Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels
 
conference paper

A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels

Abbe, Emmanuel  
•
Sandon, Colin Peter  
January 1, 2023
2023 Ieee 64Th Annual Symposium On Foundations Of Computer Science, Focs
64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

In 1948, Shannon used a probabilistic argument to show that there exist codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major progress was made towards establishing this conjecture over the last decades, with various branches of discrete mathematics involved such as combinatorial bounds, sharp thresholds, hypercontractivity, additive combinatorics and polarization theory. In particular, the special case of the erasure channel was settled by Kudekar at al., relying on Bourgain-Kalai's sharp threshold theorem for symmetric monotone properties. The main case of error channels remained however unsettled, due in particular to the property being non-monotone and the lack of techniques to obtain fast local error decay up to capacity, despite the notable vanishing bound on the local error from Reeves-Pfister.|This paper closes the conjecture's proof. The main ingredient is a new recursive boosting framework for coding, where codewords are decoded by aggregating restrictions on a 'subspace-sunflower' structure, analogous to the structure from Erdos-Rado 1960. The dependencies between the sunflower petals are handled with an L-2 and L-4 Boolean Fourier analysis, and a list-decoding argument with a weight enumerator bound from Sberlo-Shpilka is used to control the global error from the local one. For the local error, while monotonicity does not apply, we show that a 'weak threshold' result still holds using solely symmetries. This gives in particular a shortened and tightened argument for the vanishing local error result, and with prior works, it also implies the strong wire-tap secrecy of RM codes on pure-state classical-quantum channels.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/FOCS57990.2023.00020
Web of Science ID

WOS:001137125900014

Author(s)
Abbe, Emmanuel  
Sandon, Colin Peter  
Date Issued

2023-01-01

Publisher

Ieee Computer Soc

Publisher place

Los Alamitos

Published in
2023 Ieee 64Th Annual Symposium On Foundations Of Computer Science, Focs
ISBN of the book

979-8-3503-1894-4

Start page

177

End page

193

Subjects

Coding

•

Shannon Capacity

•

Reed-Muller Codes

•

Boosting

•

Sunflowers

•

Fourier Analysis

•

Symmetries

•

Thresholds

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MDS1  
Event nameEvent placeEvent date
64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

Santa Cruz, CA

NOV 06-09, 2023

Available on Infoscience
February 23, 2024
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/205250
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés