Algorithms for Modular Counting of Roots of Multivariate Polynomials

Given a multivariate polynomial P(X ₁,…,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.