Reed-Muller Codes

DOI10.1561/0100000123OpenAlexW4317392398MaRDI QIDQ5870775

Ori Sberlo, Min Ye, Emmanuel Abbe, Amir Shpilka

Publication date: 23 January 2023

Published in: Foundations and Trends® in Communications and Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0100000123

zbMATH Keywords

Reed-Muller codesweight enumeratordecodinghypercontractivitypolarization theorycapacity-achieving propertiesthresholds of Boolean functions

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02)

Cites Work

• Noise sensitivity of Boolean functions and applications to percolation
• On codes decoding a constant fraction of errors on the BSC
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Random low-degree polynomials are hard to approximate
• The coding of messages subject to chance errors
• Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On decoding by error location and dependent sets of error positions
• Alternating bilinear forms over GF(q)
• Self-testing/correcting with applications to numerical problems
• Influences of variables and threshold intervals under group symmetries
• Decoding of Reed-Muller codes with a large number of errors
• General constructions for information-theoretic private information retrieval
• Extractors from Reed-Muller codes
• Discrete Isoperimetric Inequalities and the Probability of a Decoding Error
• Optimal Testing of Multivariate Polynomials over Small Prime Fields
• Polarization and Polar Codes
• 2-Server PIR with Sub-Polynomial Communication
• Unified Scaling of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error Floors
• Universal Polarization
• Reed–Muller Codes for Random Erasures and Errors
• Restricted Isometry Property of Random Subdictionaries
• List Decoding of Polar Codes
• Polar Codes: Speed of Polarization and Polynomial Gap to Capacity
• Finite-Length Scaling for Polar Codes
• Moderate Deviations in Channel Coding
• Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization
• How to share a secret
• Testing low-degree polynomials over prime fields
• Pseudorandom Bits for Polynomials
• Proof verification and the hardness of approximation problems
• Private information retrieval
• A class of low-rate nonlinear binary codes
• On the strong converse of the coding theorem for symmetric channels without memory
• Testing Polynomials over General Fields
• Modern Coding Theory
• Testing Reed–Muller Codes
• Extrinsic information transfer functions: model and erasure channel properties
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Recursive Decoding and Its Performance for Low-Rate Reed–Muller Codes
• Soft-decision decoding of Reed-Muller codes: a simplified algorithm
• Soft-decision decoding of Reed-Muller codes: recursive lists
• The Simplex Codes and Other Even-Weight Binary Linear Codes for Error Correction
• Error-Correction Capability of Binary Linear Codes
• A New Upper Bound on the Block Error Probability After Decoding Over the Erasure Channel
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Fundamentals of Error-Correcting Codes
• Reed Muller Sensing Matrices and the LASSO
• Maxwell Construction: The Hidden Bridge Between Iterative and Maximuma PosterioriDecoding
• Optimal soft decision block decoders based on fast Hadamard transform
• Efficient dispersal of information for security, load balancing, and fault tolerance
• Hypothesis testing and information theory
• On the weight enumeration of weights less than 2.5d of Reed—Muller codes
• IP = PSPACE
• The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes
• Error-locating pairs for cyclic codes
• Bounds on the decoding error probability of binary linear codes via their spectra
• Random coding techniques for nonrandom codes
• Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields
• Error Detecting and Error Correcting Codes
• Random codes: minimum distances and error exponents
• Every monotone graph property has a sharp threshold
• Binary Linear Codes With Optimal Scaling: Polar Codes With Large Kernels
• Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
• Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels
• Reed–Muller Codes: Theory and Algorithms
• Polar Codes’ Simplicity, Random Codes’ Durability
• Almost-Reed–Muller Codes Achieve Constant Rates for Random Errors
• Recursive Projection-Aggregation Decoding of Reed-Muller Codes
• Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity
• On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures
• Analysis of Boolean Functions
• An Upper Bound on $\ell_q$ Norms of Noisy Functions
• Construction of Polar Codes With Sublinear Complexity
• Weight Distribution and List-Decoding Size of Reed–Muller Codes
• Efficiently Decoding Reed–Muller Codes From Random Errors
• Channel Coding Rate in the Finite Blocklength Regime
• How to Construct Polar Codes
• Reed–Muller Codes Achieve Capacity on Erasure Channels
• Reed-Muller codes achieve capacity on erasure channels
• Probability and Computing
• Stable signal recovery from incomplete and inaccurate measurements
• A simple derivation of the coding theorem and some applications
• An optimum nonlinear code
• New generalizations of the Reed-Muller codes--I: Primitive codes
• On the weight structure of Reed-Muller codes
• Weight enumerator for second-order Reed-Muller codes
• Class of algorithms for decoding block codes with channel measurement information
• Lower bounds to error probability for coding on discrete memoryless channels. I
• The random coding bound is tight for the average code (Corresp.)
• Locally Decodable Codes
• Algebraic Codes for Data Transmission
• Compressed sensing