Fast Probabilistic Algorithms for Verification of Polynomial Identities

1980/10/01 by Jacob T. Schwartz · 15 citations
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Logic, programming, and type systems #Citation #Computer science #Probabilistic logic #Algorithm #Theoretical computer science #Artificial intelligence #Library science

paper · pdf · doi:10.1145/322217.322225

openalex publication_date 1980/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

The starthng success of the Rabm-Strassen-Solovay pnmahty algorithm, together with the intriguing foundattonal posstbthty that axtoms of randomness may constttute a useful fundamental source of mathemaucal truth independent of the standard axmmaUc structure of mathemaUcs, suggests a wgorous search for probabdisuc algonthms In dlustratmn of this observaUon, vanous fast probabdlsttc algonthms, with probability of correctness guaranteed a prion, are presented for testing polynomial ldentmes and propemes of systems of polynomials. Ancdlary fast algorithms for calculating resultants and Sturm sequences are given. Probabilistlc calculatton in real anthmetlc, prewously considered by Davis, is justified ngorously, but only in a special case. Theorems of elementary geometry can be proved much more efficiently by the techmques presented than by any known arttficml-mtelhgence approach

Citations

• Die Frage der endlich vielen Schritte in der Theorie der Polynomideale

Cited by

• Algorithms and fine-grained complexity for nondeterministic and symmetric difference automata
• A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems
• Computing points in connected components defined by a real inequation: algorithms, complexity and implementations, Part I
• 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
• On the genericity of maximum rank distance and Gabidulin codes
• Constructing a Distance Sensitivity Oracle in O(n^2.5794M) Time
• Proof Complexity Lower Bounds from Algebraic Circuit Complexity
• Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
• Deterministic Depth-4 PIT and Normalization
• Proof verification and the hardness of approximation problems
• Proof verification and hardness of approximation problems
• Coin Flipping in Dynamic Programming Is Almost Useless
• Schwartz–Zippel lemma [wikipedia]