Deterministic polynomial identity tests for multilinear bounded-read formulae

DOI10.1007/S00037-015-0097-4zbMath1346.68105OpenAlexW2003659538MaRDI QIDQ901932

N. E. Zubov

Publication date: 6 January 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-015-0097-4

zbMATH Keywords

derandomizationarithmetic circuitsbounded-depth circuitsidentity testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items (6)

Sums of read-once formulas: how many summands are necessary? ⋮ Recent Results on Polynomial Identity Testing ⋮ Algebraic Independence and Blackbox Identity Testing ⋮ Sums of Read-Once Formulas: How Many Summands Suffice? ⋮ A note on parameterized polynomial identity testing using hitting set generators ⋮ Characterizing Arithmetic Read-Once Formulae

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Lower bounds and separations for constant depth multilinear circuits
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• The ideal membership problem and polynomial identity testing
• Deterministically testing sparse polynomial identities of unbounded degree
• The complexity of partial derivatives
• A probabilistic remark on algebraic program testing
• Lower bounds on arithmetic circuits via partial derivatives
• Arithmetic Circuits: A Chasm at Depth 3
• An Almost Optimal Rank Bound for Depth-3 Identities
• Arithmetic Circuits: A survey of recent results and open questions
• Primality and identity testing via Chinese remaindering
• Diagonal Circuit Identity Testing and Lower Bounds
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• Improved Polynomial Identity Testing for Read-Once Formulas
• Progress on Polynomial Identity Testing - II
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Randomness efficient identity testing of multivariate polynomials
• Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in
• Jacobian hits circuits
• Black-box identity testing of depth-4 multilinear circuits
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Depth-3 arithmetic circuits over fields of characteristic zero

This page was built for publication: Deterministic polynomial identity tests for multilinear bounded-read formulae