Existence of short proofs for nondivisibility of sparse polynomials under the extended riemann hypothesis

Dima Yu Grigoriev, Marek Karpinski, Andrew M. Odlyzko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We display an existence of the short (polynomial size) proofs for nondivisibility of two sparse multivariate polynomials under the Extended Riemann Hyphothe-sis (ERH). The divisibility problem is closely related to the rational interpolation problem (whose complexity bounds were determined in [GKS 90] and [GK 91]). In this setting we assume that a rational function is given by a black box (see e.g. [KT 88, GKS 90, K 89]) for evaluating it. We prove also that, surprisingly, the problem of deciding whether a rational function given by a black box equals a polynomial belongs to the parallel class NC (see e.g. [KR 90]), provided we know the degree of some sparse representation of it.

Original languageEnglish (US)
Title of host publicationPapers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992
EditorsPaul S. Wang
PublisherAssociation for Computing Machinery
Pages117-122
Number of pages6
ISBN (Electronic)0897914899
DOIs
StatePublished - Aug 1 1992
Event1992 International Symposium on Symbolic and Algebraic Computation, ISSAC 1992 - Berkeley, United States
Duration: Jul 27 1992Jul 29 1992

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
VolumePart F129620

Other

Other1992 International Symposium on Symbolic and Algebraic Computation, ISSAC 1992
CountryUnited States
CityBerkeley
Period7/27/927/29/92

Fingerprint Dive into the research topics of 'Existence of short proofs for nondivisibility of sparse polynomials under the extended riemann hypothesis'. Together they form a unique fingerprint.

  • Cite this

    Grigoriev, D. Y., Karpinski, M., & Odlyzko, A. M. (1992). Existence of short proofs for nondivisibility of sparse polynomials under the extended riemann hypothesis. In P. S. Wang (Ed.), Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992 (pp. 117-122). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC; Vol. Part F129620). Association for Computing Machinery. https://doi.org/10.1145/143242.143287