On computing sparse shifts for univariate polynomials

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On computing sparse shifts for univariate polynomials

Full text

Pdf (679 KB)

Source

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

Oxford, United Kingdom

Pages: 108 - 113

Year of Publication: 1994

ISBN:0-89791-638-7

Authors

Y. N. Lakshman	Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA
B. David Saunders	Department of Computer and Information Sciences, University of Delaware, Newark, DE

Sponsor

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 4, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/190347.190373 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.

	1	Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
	2	A. Borodin , P. Tiwari, On the decidability of sparse univariate polynomial interpolation, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.535-545, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100292]
	3	Pried, M.D., and MacRae, R.E., (1969), "On the invariance of chains of fields," Ill. Jour. Math., 13, 165-171.
	4	von zur Gathen, J., Kozen, D., and Landau, S. (1987), "Functional decomposition of polynomials," Proc. 28th IEEE Symp. Pound. Comp. Sci., Nov 1987, pp. 127-13t.
	5	Michael Clausen , Andreas Dress , Johannes Grabmeier , Marek Karpinski, On Zero-Testing and Interpolation of $k$-sparse Multivariate Polynomials over Finite Fields, University of Bonn, 1988
	6	Grigoriev, D. Yu. and Karpinski, M. (1987), "The matching problem for bipartite graphs with polynomia}ly bounded permanents is in NC," Proc. 28th IEEE Syrup. Foundations Comp. Sci., pp. 166-172.
	7	Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
	8	Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Rational Interpolation, SIAM Journal on Computing, v.23 n.1, p.1-12, Feb. 1994 [doi>10.1137/S0097539791194069]
	9	Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Real Algebraic Function Interpolation, University of Bonn, 1992
	10	Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, The interpolation problem for k-sparse sums of eigenfunctions of operators, Advances in Applied Mathematics, v.12 n.1, p.76-81, March 1991 [doi>10.1016/0196-8858(91)90005-4]
	11	Dima Grigoriev , Marek Karpinski, A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.162-169, May 10-14, 1993
	12	Dima Yu. Grigoriev , Marek Karpinski , Andrew M. Odlyzko, Existence of short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis, Papers from the international symposium on Symbolic and algebraic computation, p.117-122, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143287]
	13	E. Kaltofen, Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.443-452, January 1987, New York, New York, United States [doi>10.1145/28395.28443]
	14	Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
	15	Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
	16	Kaplanski, I. (1957), "An introduction to differential algebra," Hermann, Paris.
	17	Y. N. Lakshman , B. David Saunders, Sparse Polynomial Interpolation in Nonstandard Bases, SIAM Journal on Computing, v.24 n.2, p.387-397, April 1995 [doi>10.1137/S0097539792237784]
	18	Lakshman, Y.N., and Saunders, B.D., (1993), "On computing sparse shifts for univariate polynomials," Tech. Rep., Dept. of Math. Comp. Sci., Drexel University, Philadelphia, PA.
	19	Loos, R. (1983), "Computing rational zeros of integral polynomials by p-adic expansion," SIAM J.Comp., Vol. 12, pp. 286- 293.
	20	Yishay Mansour, Randomized Interpolation and Approximation of Sparse Polynomials, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.261-272, July 13-17, 1992
	21	Muir, T. (1960, enlarged by Metzler, H.), "A treatise on the theory of determinants,", Dover Publishing Inc., New York.
	22	Ritt, J.F., (1922), "Prime and composite polynomials," Trans. Amer. Math. Soc. 23, pp. 51-66.
	23	Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]

CITED BY 3

	D. Grigoriev, Testing shift-equivalence of polynomials using quantum machines, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.49-54, July 24-26, 1996, Zurich, Switzerland
	Angel Díaz , Erich Kaltofen, On computing greatest common divisors with polynomials given by black boxes for their evaluations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.232-239, July 10-12, 1995, Montreal, Quebec, Canada
	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