The Monomial Ideal Membership Problem and Polynomial Identity Testing

DOI10.1007/978-3-540-77120-3_69zbMath1193.68125MaRDI QIDQ5387813

V. 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

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

68W20: Randomized algorithms

Related Items

Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, The ideal membership problem and polynomial identity testing, Recent Results on Polynomial Identity Testing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• PRIMES is in P
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Polynomial identity testing for depth 3 circuits
• Primality and identity testing via Chinese remaindering
• Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Algebraic methods for interactive proof systems
• Membership in polynomial ideals over Q is exponential space complete
• Derandomizing polynomial identity tests means proving circuit lower bounds