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.68133MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Unnamed Item, Sylvester-Gallai type theorems for quadratic polynomials, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Depth-4 Identity Testing and Noether’s Normalization Lemma, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond, Subexponential size hitting sets for bounded depth multilinear formulas, Read-once polynomial identity testing, Towards dimension expanders over finite fields, Deterministic polynomial identity tests for multilinear bounded-read formulae, Deterministic identity testing for sum of read-once oblivious arithmetic branching programs, Improved hitting set for orbit of ROABPs, Lossless dimension expanders via linearized polynomials and subspace designs, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, Recent Results on Polynomial Identity Testing, Algebraic Independence and Blackbox Identity Testing
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
