SwissMAP Logo
Log in
  • About us
    • Organization
    • Professors
    • Senior Researchers
    • Postdocs
    • PhD Students
    • Alumni
  • News & Events
    • News
    • Events
    • Online Events
    • Videos
    • Newsletters
    • Press Coverage
    • Perspectives Journal
    • Interviews
  • Research
    • Basic Notions
    • Phase III Directions
    • Phases I & II Projects
    • Publications
    • SwissMAP Research Station
  • Awards, Visitors & Vacancies
    • Awards
    • Innovator Prize
    • Visitors
    • Vacancies
  • Outreach & Education
    • Masterclasses & Doctoral Schools
    • Mathscope
    • Maths Club
    • Athena Project
    • ETH Math Youth Academy
    • SPRING
    • Junior Euler Society
    • General Relativity for High School Students
    • Outreach Resources
    • Exhibitions
    • Previous Programs
    • Events in Outreach
    • News in Outreach
  • Equal Opportunities
    • Mentoring Program
    • Financial Support
    • SwissMAP Scholars
    • Events in Equal Opportunities
    • News in Equal Opportunities
  • Contact
    • Corporate Design
  • Basic Notions
  • Phase III Directions
  • Phases I & II Projects
  • Publications
  • SwissMAP Research Station

Polynomial Freiman-Ruzsa, Reed-Muller codes and Shannon capacity

Emmanuel Abbe, Colin Sandon, Vladyslav Shashkov, Maryna Viazovska

20/11/24 Published in : arXiv:2411.13493

In 1948, Shannon used a probabilistic argument to show the existence of codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, based on polynomial evaluations, conjectured shortly after to achieve capacity. The conjecture led to decades of activity involving various areas of mathematics and the recent settlement by [AS23] using flower set boosting. In this paper, we provide an alternative proof of the weak form of the capacity result, i.e., that RM codes have a vanishing local error at any rate below capacity. Our proof relies on the recent Polynomial Freiman-Ruzsa conjecture's proof [GGMT23] and an entropy extraction approach similar to [AY19]. Further, a new additive combinatorics conjecture is put forward which would imply the stronger result with vanishing global error. We expect the latter conjecture to be more directly relevant to coding applications.

Entire article

Phase I & II research project(s)

  • Geometry, Topology and Physics

Phase III direction(s)

  • Statistical Mechanics and Random Structures

Lower bounds on the top Lyapunov exponent for linear PDEs driven by the 2D stochastic Navier-Stokes equations

\mathrm{SL}(2,\mathbb{R}) Gauge Theory, Hyperbolic Geometry and Virasoro Coadjoint Orbits

  • Leading house

  • Co-leading house


The National Centres of Competence in Research (NCCRs) are a funding scheme of the Swiss National Science Foundation

© SwissMAP 2025 - All rights reserved