Probabilistic algorithms for sparse polynomials

1979/01/01 by Richard Zippel · 473 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Algorithm #Artificial intelligence #Class (philosophy) #Computer science #Data Management and Algorithms #Lemma (botany) #Modular design #Probabilistic analysis of algorithms #Probabilistic logic #Programming language #Rest (music) #Theoretical computer science

paper · doi:10.1007/3-540-09519-5_73

published in Lecture Notes in Computer Science, 216-226 (Springer Berlin Heidelberg)

crossref issued 1979/01/01 · crossref published 1979/01/01 · crossref published-print 1979/01/01 · openalex publication_date 1979/01/01 · crossref published-online 2005/05/24 · crossref created 2012/02/25 · crossref deposited 2020/11/17 · openalex created_date 2025/10/10 · crossref indexed 2026/08/04 · openalex updated_date 2026/08/05

Citations

• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors

Cited by

• Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard
• Primality and identity testing via Chinese remaindering
• On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• Can every randomized algorithm be derandomized?
• Deterministic polynomial identity testing in non commutative models
• FORM version 4.0
• Constructing a Distance Sensitivity Oracle in O(n^2.5794M) Time
• Proof Complexity Lower Bounds from Algebraic Circuit Complexity
• Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good
• Deterministic Depth-4 PIT and Normalization
• Detecting lacunary perfect powers and computing their roots
• Sparse Polynomial Interpolation Based on Diversification
• Coin Flipping in Dynamic Programming Is Almost Useless
• Faster multivariate integration in D-modules
• Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
• Deterministic factorization of constant-depth algebraic circuits in subexponential time
• Streaming word problems
• Schwartz–Zippel lemma [wikipedia]