Minimum Distance Decoding for Reed-Muller Codes using Projection-Aggregation

This paper shows that projection-aggregation (PA) decoding of Reed-Muller (RM) codes can decode up to half the minimum distance d efficiently. By generalizing the false vote matrix from 1-dimensional to higher-dimensional subspaces, we prove that projecting onto disjoint subspaces, regardless of their dimensions, provides at most d/2 - 1 false votes for each codeword bit. Thus, d disjoint subspaces guarantee the correction for errors of d/2 - 1 or less. Moreover, the flexibility in subspace dimensions allows projecting into repetition codes directly, resulting in decoding efficiency. Finally, we prove that PA decoding with d disjoint subspaces decodes up to half the minimum distance in O(n√ n ) for RM codes of length n and half rate or less.