Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

DOI10.1007/S00493-011-2537-3zbMath1274.68133OpenAlexW2104644213MaRDI QIDQ654006

Amir Shpilka, Zohar S. Karnin

Publication date: 20 December 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-011-2537-3

zbMATH Keywords

arithmetic circuitsidentity testing algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ Towards dimension expanders over finite fields ⋮ Read-once polynomial identity testing ⋮ Lossless dimension expanders via linearized polynomials and subspace designs ⋮ Recent Results on Polynomial Identity Testing ⋮ Algebraic Independence and Blackbox Identity Testing ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved hitting set for orbit of ROABPs ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Learning sparse multivariate polynomials over a field with queries and counterexamples.
• Matching is as easy as matrix inversion
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• The complexity of sparse polynomial interpolation over finite fields
• On some approximation problems concerning sparse polynomials over finite fields
• Deterministic polynomial identity testing in non-commutative models
• Deterministic extractors for affine sources over large fields
• Polynomial identity testing for depth 3 circuits
• Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
• An Almost Optimal Rank Bound for Depth-3 Identities
• Primality and identity testing via Chinese remaindering
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Improved Polynomial Identity Testing for Read-Once Formulas
• Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• Reducing Randomness via Irrational Numbers
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Randomness efficient identity testing of multivariate polynomials
• The Monomial Ideal Membership Problem and Polynomial Identity Testing
• 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: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in