The ideal membership problem and polynomial identity testing

DOI10.1016/j.ic.2009.06.003zbMath1190.68027OpenAlexW2034027554MaRDI QIDQ963063

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

ideal membershiparithmetic circuitspolynomial identity testing

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)

Related Items (7)

Unnamed Item ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Efficient Black-Box Identity Testing for Free Group Algebras ⋮ Read-once polynomial identity testing ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Unnamed Item ⋮ Univariate ideal membership parameterized by rank, degree, and number of generators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching is as easy as matrix inversion
• 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
• IP = PSPACE
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: The ideal membership problem and polynomial identity testing