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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (374 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Papers from the international symposium on Symbolic and algebraic computation table of contents

Berkeley, California, United States

Pages: 117 - 122

Year of Publication: 1992

ISBN:0-89791-489-9

Authors

Dima Yu. Grigoriev
Marek Karpinski
Andrew M. Odlyzko

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 7, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/143242.143287 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BCH 86	Paul W Beame , Stephen A Cook , H James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing, v.15 n.4, p.994-1003, Nov. 1986 [doi>10.1137/0215070]
	CG 82	A. L. Chistov and D. Yu. Grigoriev, Polynomial-lime factoring mullivariable polynomials over a global field, Preprint LOMI, E-5-82, Leningrad, 1982.
	GK 91	Dima Yu. Grigoriev , Marek Karpinski, Algorithms for sparse rational interpolation, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.7-13, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120696]
	GKS 90	D. Yu. Grigoriev, M. Karpinski, and M. Singer, Interpolation of sparse rational functions without knowing bounds on exponents, Proc. 31 FOCS, IEEE, 1990, pp. 840-846.
	K 89	Marek Karpinski, Boolean Complexity of Algebraic Interpolation Problems, Proceedings of the 2nd Workshop on Computer Science Logic, p.138-147, October 03-07, 1988
	KT 88	E. Kaltofen and B. Trager, Computing with polynomials gzven by black-boxes for their evaluation: GCD, factorization separation of numerators and denominators, Proc. 29 FOCS, IEEE, 1988, pp. 296-305.
	KR 90	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	LO 77	J.C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, in Algebraic Number Fields, A. FrShlich, ed., Academic Press, 1977, pp. 409-464.
	L 82	R. Loos, Generalized polynom,al remainder sequences, in Computer Algebra: Symbolic and Algebraic Computation, B. Buchberger, G. E. Collins, and R. Loos, eds., Springer, 1982, pp. 115-137.
	M 82	M. Mignotte, Some useful bounds, in Computer Algebra: Symbolic and Algebraic Computation, B. Buchberger, G. E. Collins, and R. Loos, eds., Springer, 1982, pp. 259-263.
	M 86	K Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.338-339, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12164]
	P 77a	D. Plaisted, Sparse complex polynom,als and polynomial reduc~bzlity, J. Comput. Syst. Sci., 14, 1977, pp. 210-221.
	P 77b	D. Plaisted, New NP-hard and NP-complete polynomial and integer divisibility problems, Proc. 18 FOCS, IEEE, 1977, pp. 241-253.
	W 84	P.J. Weinberger, F, ndzng the Numbers of factors of a polynomial, J. Algorithms 5, 1984, pp. 180-186.

CITED BY 2

	Y. N. Lakshman , B. David Saunders, On computing sparse shifts for univariate polynomials, Proceedings of the international symposium on Symbolic and algebraic computation, p.108-113, July 20-22, 1994, Oxford, United Kingdom
	Dima Yu. Grigoriev , Y. N. Lakshman, Algorithms for computing sparse shifts for multivariate polynomials, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.96-103, July 10-12, 1995, Montreal, Quebec, Canada