The ideal membership problem and polynomial identity testing

DOI10.1016/J.IC.2009.06.003MaRDI QIDQ963063zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Partha Mukhopadhyay

Publication date 8 April 2010

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

Full work available at URL https://doi.org/10.1016/j.ic.2009.06.003

zbMATH Keywords

arithmetic circuitspolynomial identity testingideal membership

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomial rings and ideals; rings of integer-valued polynomials (13F20)

Recommendations

• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• Polynomial identity testing for depth 3 circuits
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• Deterministically testing sparse polynomial identities of unbounded degree
• Some complexity results for polynomial ideals

Cites work

• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 108068 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• IP = PSPACE
• Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
• Matching is as easy as matrix inversion
• PRIMES is in P
• Polynomial identity testing for depth 3 circuits
• Primality and identity testing via Chinese remaindering
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• The complexity of the word problems for commutative semigroups and polynomial ideals

Cited in

(13)

• The complexity of the ideal membership problem for constrained problems over the Boolean domain
• Read-once polynomial identity testing
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• Linear independence, alternants, and applications
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• The Identity Correspondence Problem and Its Applications
• On reconstruction and testing of read-once formulas
• Efficient Black-Box Identity Testing for Free Group Algebras
• Univariate ideal membership parameterized by rank, degree, and number of generators
• scientific article; zbMATH DE number 7559384 (Why is no real title available?)
• scientific article; zbMATH DE number 7724189 (Why is no real title available?)
• scientific article; zbMATH DE number 7561312 (Why is no real title available?)
• Depth-4 identity testing and Noether's normalization lemma

This page was built for publication: The 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 Q963063)