List-decoding reed-muller codes over small fields

ABSTRACT

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.

REFERENCES

• 1: A. Akavia, S. Goldwasser, and S. Safra, Proving hard-core predicates using list decoding, in Proc. 44th IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.
• 2: N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron, Testing Reed-Muller codes, IEEE Transactions on Information Theory, 51(11) (2005), pp. 4032--4039.
• 3: S. Arora and M. Sudan, Improved low-degree testing and its applications., Combinatorica, 23 (2003), pp. 365--426.
• 4: M. Blum, M. Luby, and R. Rubinfeld, Self-testing/correcting with applications to numerical problems, J. Comput. Syst. Sci., 47(3) (1993), pp. 549--595.
• 5: A. Bogdanov and E. Viola, Pseudorandom bits for polynomials, in Proc. 48th IEEE Symp. on Foundations of Computer Science (FOCS'07), 2007.
• 6: R. Calderbank, A. Gilbert, and M. Strauss, List decoding of noisy Reed-Muller-like codes, arXiv:cs/0607098v2 [cs.DS], (2006).
• 7: I. Dumer, Decoding of Reed-Muller codes with polylogarithmic complexity, in WISICT '04: Proceedings of the winter international synposium on Information and communication technologies, 2004, pp. 1--6.
• 8: Z. Dvir and A. Shpilka, Noisy interpolating sets for low degree polynomials, in Proc. 23rd IEEE Conference on Computational Complexity, to appear, 2008.
• 9: P. Elias, List decoding for noisy channels, Tech. Rep. 335, Research Laboratory of Electronics, MIT, 1957.
• 10: O. Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, 2000.
• 11: O. Goldreich and L. Levin, A hard-core predicate for all one-way functions., in Proc. 21st ACM Symposium on the Theory of Computing, 1989, pp. 25--32.
• 12: O. Goldreich, R. Rubinfeld, and M. Sudan, Learning polynomials with queries: The highly noisy case., SIAM J. Discrete Math., 13 (2000), pp. 535--570.
• 13: V. Guruswami, List Decoding of Error-Correcting Codes, vol. 3282 of Lecture Notes in Computer Science, Springer, 2004.
• 14: łeavevmoderule height 2pt depth -1.6pt width 23pt, Algorithmic Results in List Decoding, vol. 2 of Foundations and Trends in Theoretical Computer Science, Now Publishers, 2006.
• 15: V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and Algebraic-Geometric codes., IEEE Transactions on Information Theory, 45(6) (1999), pp. 1757--1767.
• 16: J. Jackson, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, Journal of Computer and System Sciences, 55 (1997), pp. 414--440.
• 17: S. M. Johnson, A new upper bound for error-correcting codes, IEEE Transactions on Information Theory, 8 (1962), pp. 203--207.
• 18: Improved asymptotic bounds for error-correcting codes, IEEE Transactions on Information Theory, 9 (1963), pp. 198--205.
• 19: T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes, IEEE Transactions on Information Theory, 16(6) (1970), pp. 752--759.
• 20: E. Kushilevitz and Y. Mansour, Learning decision trees using the Fourier spectrum, SIAM Journal of Computing, 22(6) (1993), pp. 1331--1348.
• 21: F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
• 22: Y. Mansour, Learning Boolean functions via the Fourier transform, Theoretical Advances in Neural Computation and Learning, (1994), pp. 391--424.
• 23: R. Pellikaan and X. Wu, List decoding of q-ary Reed-Muller codes, IEEE Transactions on Information Theory, 50(4) (2004), pp. 679--682.
• 24: A. Samorodnitsky, Low-degree tests at large distances, in Proc. 39th ACM Symposium on the Theory of Computing (STOC'07), 2007, pp. 506--515.
• 25: M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound., Journal of Complexity, 13 (1997), pp. 180--193.
• 26: List decoding: Algorithms and applications, SIGACT News, 31 (2000), pp. 16--27.
• 27: M. Sudan, L. Trevisan, and S. P. Vadhan, Pseudorandom generators without the XOR lemma., J. Comput. Syst. Sci., 62 (2001), pp. 236--266.
• 28: L. Trevisan, List-decoding using the XOR lemma, in Proc. $44^th$ IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003, p. 126.
• 29: Some applications of coding theory in computational complexity., Quaderni di Matematica, 13 (2004), pp. 347--424.
• 30: J. Wozencraft, List decoding, Tech. Rep. 48:90-95, Quarterly Progress Report, Research Laboratory of Electronics, MIT, 1958.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
fitting polynomials, list-decoding, reed-muller codes, self-correctors