Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
From MaRDI portal
Publication:654006
DOI10.1007/s00493-011-2537-3zbMath1274.68133OpenAlexW2104644213MaRDI QIDQ654006
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
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
