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

Dima Yu Grigoriev; Marek Karpinski; Andrew M. Odlyzko

doi:10.1145/143242.143287

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

Dima Yu Grigoriev, Marek Karpinski, Andrew M. Odlyzko

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 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 language	English (US)
Title of host publication	Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992
Editors	Paul S. Wang
Publisher	Association for Computing Machinery
Pages	117-122
Number of pages	6
ISBN (Electronic)	0897914899
DOIs	https://doi.org/10.1145/143242.143287
State	Published - Aug 1 1992
Event	1992 International Symposium on Symbolic and Algebraic Computation, ISSAC 1992 - Berkeley, United States Duration: Jul 27 1992 → Jul 29 1992

Publication series

Name	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
Volume	Part F129620

Other

Other	1992 International Symposium on Symbolic and Algebraic Computation, ISSAC 1992
Country/Territory	United States
City	Berkeley
Period	7/27/92 → 7/29/92

Bibliographical note

Publisher Copyright:
© 1992 ACM.

Publisher link

10.1145/143242.143287

Find It

Find It at U of M Libraries

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

Existence of short proofs for nondivisibility of sparse polynomials under the extended riemann hypothesis. / Grigoriev, Dima Yu; Karpinski, Marek; Odlyzko, Andrew M.
Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992. ed. / Paul S. Wang. Association for Computing Machinery, 1992. p. 117-122 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC; Vol. Part F129620).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Grigoriev, DY, Karpinski, M & Odlyzko, AM 1992, Existence of short proofs for nondivisibility of sparse polynomials under the extended riemann hypothesis. in PS Wang (ed.), Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, vol. Part F129620, Association for Computing Machinery, pp. 117-122, 1992 International Symposium on Symbolic and Algebraic Computation, ISSAC 1992, Berkeley, United States, 7/27/92. https://doi.org/10.1145/143242.143287

Grigoriev DY, Karpinski M, Odlyzko AM. Existence of short proofs for nondivisibility of sparse polynomials under the extended riemann hypothesis. In Wang PS, editor, Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992. Association for Computing Machinery. 1992. p. 117-122. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). doi: 10.1145/143242.143287

Grigoriev, Dima Yu ; Karpinski, Marek ; Odlyzko, Andrew M. / Existence of short proofs for nondivisibility of sparse polynomials under the extended riemann hypothesis. Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992. editor / Paul S. Wang. Association for Computing Machinery, 1992. pp. 117-122 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

@inproceedings{97ad3ce03d0e4ef9853b00edc5f6a55e,

title = "Existence of short proofs for nondivisibility of sparse polynomials under the extended riemann hypothesis",

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.",

author = "Grigoriev, {Dima Yu} and Marek Karpinski and Odlyzko, {Andrew M.}",

note = "Publisher Copyright: {\textcopyright} 1992 ACM.; 1992 International Symposium on Symbolic and Algebraic Computation, ISSAC 1992 ; Conference date: 27-07-1992 Through 29-07-1992",

year = "1992",

month = aug,

day = "1",

doi = "10.1145/143242.143287",

language = "English (US)",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

publisher = "Association for Computing Machinery",

pages = "117--122",

editor = "Wang, {Paul S.}",

booktitle = "Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992",

}

TY - GEN

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

AU - Grigoriev, Dima Yu

AU - Karpinski, Marek

AU - Odlyzko, Andrew M.

PY - 1992/8/1

Y1 - 1992/8/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0007057584&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0007057584&partnerID=8YFLogxK

U2 - 10.1145/143242.143287

DO - 10.1145/143242.143287

M3 - Conference contribution

AN - SCOPUS:0007057584

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 117

EP - 122

BT - Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC 1992

A2 - Wang, Paul S.

PB - Association for Computing Machinery

T2 - 1992 International Symposium on Symbolic and Algebraic Computation, ISSAC 1992

Y2 - 27 July 1992 through 29 July 1992

ER -

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

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this