A case of depth-3 identity testing, sparse factorization and duality
From MaRDI portal
Publication:1947039
DOI10.1007/s00037-012-0054-4zbMath1311.68201MaRDI QIDQ1947039
Nitin Saxena, Ramprasad Saptharishi, Chandan Saha
Publication date: 11 April 2013
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-012-0054-4
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
94C12: Fault detection; testing in circuits and networks
Related Items
Unnamed Item, Unnamed Item, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Improved hitting set for orbit of ROABPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- PRIMES is in P
- Deterministic polynomial identity testing in non-commutative models
- The complexity of two problems on arithmetic circuits
- Polynomial identity testing for depth 3 circuits
- Tensor-rank and lower bounds for arithmetic formulas
- Arithmetic Circuits: A survey of recent results and open questions
- Proof verification and the hardness of approximation problems
- Primality and identity testing via Chinese remaindering
- Diagonal Circuit Identity Testing and Lower Bounds
- Progress on Polynomial Identity Testing - II
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Algebraic methods for interactive proof systems
- Randomness efficient identity testing of multivariate polynomials
- Black-box identity testing of depth-4 multilinear circuits
- Blackbox identity testing for bounded top fanin depth-3 circuits
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Derandomizing polynomial identity tests means proving circuit lower bounds
