期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals 1 − 2 q over any field F q where 2"> q 2 . This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree 2 . Previously, tight bounds for quadratic polynomials were known only for q = 2 3 ; the best bound known for other fields was the Johnson radius which is roughly 1 − 1 q . We say that a polynomial over \F q is k -dimensional if it can be expressed as a function of k linear functions. We reduce the Reed-Muller list-decoding problem to list-decoding low-dimensional polynomials and present a new Fourier-based algorithm for the low-dimensional case. The list-decoding radius achieved by this approach for degree 3 and higher depends on questions regarding the weight-distribution of the Reed-Muller code. We propose a conjecture in this regard, which if true, improves on the best known bounds for the list-decoding radius for all d and q . The conjecture holds true for \F 2 , giving an alternate proof of the main result of GKZ. Departing from previous work on Reed-Muller decoding which relies on some form of self-corrector, our work applies ideas from Fourier analysis of Boolean functions to low-degree polynomials over finite fields. We believe that the techniques used here could find other applications, we present applications to testing and learning.
q over any field F q where 2"> q 
