Deterministically testing sparse polynomial identities of unbounded degree

DOI10.1016/j.ipl.2008.09.029zbMath1191.68822OpenAlexW2100272829MaRDI QIDQ976069

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

zbMATH Keywords

derandomizationtheory of computationarithmetic circuitspolynomial identity testing

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (6)

Exact learning from an honest teacher that answers membership queries ⋮ Sparse polynomial interpolation based on derivatives ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Unnamed Item ⋮ Computing the multilinear factors of lacunary polynomials without heights ⋮ Algebraic independence in positive characteristic: A $p$-adic calculus

Cites Work

• Matching is as easy as matrix inversion
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• A probabilistic remark on algebraic program testing
• The complexity of sparse polynomial interpolation over finite fields
• On some approximation problems concerning sparse polynomials over finite fields
• PRIMES is in P
• Primality and identity testing via Chinese remaindering
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Asymptotically Optimal Hitting Sets Against Polynomials
• Pseudorandom generators for low degree polynomials
• Probabilistic checking of proofs
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Computational Complexity of Sparse Rational Interpolation
• IP = PSPACE
• Designing programs that check their work
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• Randomness efficient identity testing of multivariate polynomials
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deterministically testing sparse polynomial identities of unbounded degree