Deterministically testing sparse polynomial identities of unbounded degree

DOI10.1016/J.IPL.2008.09.029zbMATH Open1191.68822OpenAlexW2100272829MaRDI QIDQ976069FDOQ976069

Richard J. Lipton, Nisheeth K. Vishnoi, Markus Bläser, Moritz Hardt

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

zbMATH Keywords

arithmetic circuitsderandomizationtheory of computationpolynomial identity testing

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

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 (11)

• Computing the multilinear factors of lacunary polynomials without heights
• Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
• Algebraic independence in positive characteristic: A $p$-adic calculus
• 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
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• Title not available (Why is that?)
• The ideal membership problem and polynomial identity testing
• 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)