The ideal membership problem and polynomial identity testing

DOI10.1016/J.IC.2009.06.003zbMATH Open1190.68027OpenAlexW2034027554MaRDI QIDQ963063FDOQ963063

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

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

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)

Cites Work

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

Cited In (13)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient Black-Box Identity Testing for Free Group Algebras
• The complexity of the ideal membership problem for constrained problems over the Boolean domain
• Title not available (Why is that?)
• The Identity Correspondence Problem and Its Applications
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• Read-once polynomial identity testing
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• Linear independence, alternants, and applications
• On reconstruction and testing of read-once formulas
• Univariate ideal membership parameterized by rank, degree, and number of generators
• 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)