Algorithms for Modular Counting of Roots of Multivariate Polynomials |
| |
Authors: | Parikshit Gopalan Venkatesan Guruswami Richard J. Lipton |
| |
Affiliation: | (1) Georgia Tech., Atlanta, GA 30332-0280, USA;(2) University of Washington, Seattle, WA 98195-2350, USA |
| |
Abstract: | Given a multivariate polynomial P(X 1,…,X n ) over a finite field , let N(P) denote the number of roots over . The modular root counting problem is given a modulus r, to determine N r (P)=N(P)mod r. We study the complexity of computing N r (P), when the polynomial is given as a sum of monomials. We give an efficient algorithm to compute N r (P) when the modulus r is a power of the characteristic of the field. We show that for all other moduli, the problem of computing N r (P) is -hard. We present some hardness results which imply that our algorithm is essentially optimal for prime fields. We show an equivalence between maximum-likelihood decoding for Reed-Solomon codes and a root-finding problem for symmetric polynomials. P. Gopalan’s and R.J Lipton’s research was supported by NSF grant CCR-3606B64. V. Guruswami’s research was supported in part by NSF grant CCF-0343672 and a Sloan Research Fellowship. |
| |
Keywords: | Polynomials Modular counting Reed-Solomon codes |
本文献已被 SpringerLink 等数据库收录! |
|