An explicit separation of relativised random polynomial time and relativised deterministic polynomial time

DOI10.1016/0020-0190(89)90143-9zbMath0705.68054OpenAlexW2050393190MaRDI QIDQ918200

Richard Zippel

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90143-9

zbMATH Keywords

computer algebrazero testingrandom polynomial algorithms

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

The Elekes-Szabó theorem in four dimensions ⋮ Chevalley-Warning at the boundary ⋮ On triple intersections of three families of unit circles ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields

Cites Work

• Interpolating polynomials from their values
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• On relativized exponential and probabilistic complexity classes
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Unnamed Item
• Unnamed Item

This page was built for publication: An explicit separation of relativised random polynomial time and relativised deterministic polynomial time