Algorithms for modular counting of roots of multivariate polynomials

DOI10.1007/S00453-007-9097-3MaRDI QIDQ2482732zbMATH OpenOpenAlexFDO

Authors Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton

Publication date 23 April 2008

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9097-3

zbMATH Keywords

Modular countingPolynomialsReed-Solomon codes

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30) Decoding (94B35)

Recommendations

• Algorithms for Modular Counting of Roots of Multivariate Polynomials
• scientific article; zbMATH DE number 1488179
• Modular counting of rational points over finite fields
• Polynomial root finding over local rings and application to error correcting codes
• Decoding Reed-Muller codes over product sets

Cites work

• A Chevalley-Warning Approach To p-Adic Estimates of Character Sums
• Algorithmic Number Theory
• Approximating the Number of Zeroes of a GF[2] Polynomial
• Computing and Combinatorics
• Computing zeta functions of Artin-Schreier curves over finite fields. II
• Counting curves and their projections
• Counting points on elliptic curves over finite fields
• Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
• scientific article; zbMATH DE number 3845662 (Why is no real title available?)
• scientific article; zbMATH DE number 1222356 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1113820 (Why is no real title available?)
• Improvements of the Chevalley-Warning and the Ax-Katz Theorems
• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• NP is as easy as detecting unique solutions
• On ACC
• PP is as Hard as the Polynomial-Time Hierarchy
• Solvability of systems of polynomial congruences modulo a large prime
• The complexity of computing the permanent

Cited in

(7)

• Infinitely many quasi-coincidence point solutions of multivariate polynomial problems
• Polynomial root finding over local rings and application to error correcting codes
• Algorithms for Modular Counting of Roots of Multivariate Polynomials
• A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity
• Polynomial Root-Finding Algorithms and Branched Covers
• An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
• Solving polynomial systems over non-fields and applications to modular polynomial factoring

This page was built for publication: Algorithms for modular counting of roots of multivariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482732)