List-decoding reed-muller codes over small fields

We present the first local list-decoding algorithm for the r th order Reed-Muller code RM(2,m) over F for r ≥ 2. Given an oracle for a received word R: F m -< F, our randomized local list-decoding algorithm produces a list containing all degree r polynomials within relative distance (2 -r - ε) from R for any ε < 0 in time poly(m r ,ε -r ). The list size could be exponential in m at radius 2 -r , so our bound is optimal in the local setting. Since RM(2,m) has relative distance 2 -r , our algorithm beats the Johnson bound for r ≥ 2. In the setting where we are allowed running-time polynomial in the block-length, we show that list-decoding is possible up to even larger radii, beyond the minimum distance. We give a deterministic list-decoder that works at error rate below J(2 1-r ), where J(δ) denotes the Johnson radius for minimum distance δ. This shows that RM(2,m) codes are list-decodable up to radius η for any constant η < 1/2 in time polynomial in the block-length. Over small fields F q , we present list-decoding algorithms in both the global and local settings that work up to the list-decoding radius. We conjecture that the list-decoding radius approaches the minimum distance (like over F), and prove this holds true when the degree is divisible by q-1.

Authors

• Parikshit Gopalan
• Adam R. Klivans
• David Zuckerman

Keywords

• fitting polynomials
• list-decoding
• reed-muller codes
• self-correctors