Recent Results on Polynomial Identity Testing

DOI10.1007/978-3-642-20712-9_31zbMath1332.68281OpenAlexW1660158219MaRDI QIDQ3007643

Amir Shpilka

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_31

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (2)

Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• Matching is as easy as matrix inversion
• A probabilistic remark on algebraic program testing
• PRIMES is in P
• Deterministic polynomial identity testing in non-commutative models
• Polynomial identity testing for depth 3 circuits
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Primality and identity testing via Chinese remaindering
• Diagonal Circuit Identity Testing and Lower Bounds
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
• Improved Polynomial Identity Testing for Read-Once Formulas
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
• Reducing Randomness via Irrational Numbers
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• Black-box identity testing of depth-4 multilinear circuits
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Recent Results on Polynomial Identity Testing