Deterministically testing sparse polynomial identities of unbounded degree
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 2079409
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- Polynomial identity testing for depth 3 circuits
- Deterministic polynomial identity testing in non-commutative models
- New results on noncommutative and commutative polynomial identity testing
Cites work
- A probabilistic remark on algebraic program testing
- Asymptotically Optimal Hitting Sets Against Polynomials
- Computational Complexity of Sparse Rational Interpolation
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Designing programs that check their work
- Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
- Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- scientific article; zbMATH DE number 5485462 (Why is no real title available?)
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 3698383 (Why is no real title available?)
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- scientific article; zbMATH DE number 1559535 (Why is no real title available?)
- scientific article; zbMATH DE number 1775429 (Why is no real title available?)
- scientific article; zbMATH DE number 861252 (Why is no real title available?)
- scientific article; zbMATH DE number 903684 (Why is no real title available?)
- scientific article; zbMATH DE number 3105562 (Why is no real title available?)
- IP = PSPACE
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Matching is as easy as matrix inversion
- On some approximation problems concerning sparse polynomials over finite fields
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Primality and identity testing via Chinese remaindering
- PRIMES is in P
- Probabilistic checking of proofs
- Pseudorandom generators for low degree polynomials
- Randomness efficient identity testing of multivariate polynomials
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- The complexity of sparse polynomial interpolation over finite fields
Cited in
(17)- A polynomial-time dependence test for determining integer-valued solutions in multi-dimensional arrays under variable bounds
- A case of depth-3 identity testing, sparse factorization and duality
- Binomiality testing and computing sparse polynomials via witness sets
- Sparse polynomial interpolation based on derivatives
- Computing the multilinear factors of lacunary polynomials without heights
- Exact learning from an honest teacher that answers membership queries
- Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
- Randomness efficient testing of sparse black box identities of unbounded degree over the reals
- Primality and identity testing via Chinese remaindering
- scientific article; zbMATH DE number 2079409 (Why is no real title available?)
- On some computations on sparse polynomials
- Randomness efficient identity testing of multivariate polynomials
- Algebraic independence in positive characteristic: a p-adic calculus
- scientific article; zbMATH DE number 7758310 (Why is no real title available?)
- Polynomial time deterministic identity testing algorithm for Σ [3] ΠΣΠ [2] circuits via Edelstein–Kelly type theorem for quadratic polynomials
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- The ideal membership problem and polynomial identity testing
This page was built for publication: Deterministically testing sparse polynomial identities of unbounded degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976069)
