Deterministically testing sparse polynomial identities of unbounded degree
From MaRDI portal
Publication:976069
DOI10.1016/J.IPL.2008.09.029zbMATH Open1191.68822OpenAlexW2100272829MaRDI QIDQ976069FDOQ976069
Authors: Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi 
Publication date: 16 June 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2008.09.029
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
- Probabilistic checking of proofs
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- PRIMES is in P
- Title not available (Why is that?)
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
- Designing programs that check their work
- Matching is as easy as matrix inversion
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Title not available (Why is that?)
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Title not available (Why is that?)
- IP = PSPACE
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Title not available (Why is that?)
- Randomness efficient identity testing of multivariate polynomials
- Primality and identity testing via Chinese remaindering
- Pseudorandom generators for low degree polynomials
- Title not available (Why is that?)
- Computational Complexity of Sparse Rational Interpolation
- The complexity of sparse polynomial interpolation over finite fields
- On some approximation problems concerning sparse polynomials over finite fields
- Title not available (Why is that?)
- Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
- Asymptotically Optimal Hitting Sets Against Polynomials
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (15)
- Computing the multilinear factors of lacunary polynomials without heights
- Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
- Exact learning from an honest teacher that answers membership queries
- A polynomial-time dependence test for determining integer-valued solutions in multi-dimensional arrays under variable bounds
- Title not available (Why is that?)
- Binomiality testing and computing sparse polynomials via witness sets
- Randomness efficient testing of sparse black box identities of unbounded degree over the reals
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- Algebraic independence in positive characteristic: a \(p\)-adic calculus
- Primality and identity testing via Chinese remaindering
- Title not available (Why is that?)
- A case of depth-3 identity testing, sparse factorization and duality
- The ideal membership problem and polynomial identity testing
- Randomness efficient identity testing of multivariate polynomials
- Sparse polynomial interpolation based on derivatives
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)
