Computer Science/Discrete Mathematics Seminar I

We present the first local list-decoding algorithm for the r-th order Reed-Muller code RM(r,m) over F_2 for r>1 . Given an oracle for a received word R: F_2^m to F_2 , our randomized local list-decoding algorithm produces a list containing all degree r polynomials within relative distance 2^{-r} - eps from R for any eps > 0 in time poly(m^r,eps^{-r}). The list size could be exponential in m at radius 2^{-r}, so our bound is optimal in the local setting. Since RM(r,m) has relative distance 2^{-r}, our algorithm beats the Johnson bound for r>1 . 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(d) denotes the Johnson radius for minimum distance d. This shows that RM(2,m) codes are list-decodable up to radius s for any constant s < 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_2), and prove this when the degree is divisible by q-1.