The Monomial Ideal Membership Problem and Polynomial Identity Testing

DOI10.1007/978-3-540-77120-3_69MaRDI QIDQ5387813zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Partha Mukhopadhyay

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_69

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Recommendations

• The ideal membership problem and polynomial identity testing
• The complexity of testing monomials in multivariate polynomials
• scientific article; zbMATH DE number 2084924
• Monic Polynomials and Generating Ideals Efficiently
• On testing monomials in multivariate polynomials
• Complexity of membership problems of different types of polynomial ideals
• scientific article; zbMATH DE number 2079409
• Bounds for the degrees in the membership test for a polynomial ideal
• On the effective membership problem for polynomial ideals
• The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals

Cites work

• Algebraic methods for interactive proof systems
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 108068 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
• Membership in polynomial ideals over \(\mathcal{Q}\) is exponential space complete
• Polynomial identity testing for depth 3 circuits
• Primality and identity testing via Chinese remaindering
• PRIMES is in P
• The complexity of the word problems for commutative semigroups and polynomial ideals

Cited in

(7)

• Univariate ideal membership parameterized by rank, degree, and number of generators
• Recent results on polynomial identity testing
• scientific article; zbMATH DE number 7559384 (Why is no real title available?)
• Univariate ideal membership parameterized by rank, degree, and number of generators
• A test for monomial containment
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• The ideal membership problem and polynomial identity testing

This page was built for publication: The Monomial Ideal Membership Problem and Polynomial Identity Testing

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