On feasible multivariate polynomial interpolations over arbitrary fields

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On feasible multivariate polynomial interpolations over arbitrary fields

Full text

Pdf (805 KB)

Source

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

Vancouver, British Columbia, Canada

Pages: 67 - 74

Year of Publication: 1999

ISBN:1-58113-073-2

Authors

Zeljko Zilic	McGill University, Dept. of Electrical and Computer Engineering, 3480 University St., Montréal, Québec H3A 2A7, Canada
Katarzyna Radecka	McGill University, Dept. of Electrical and Computer Engineering, 3480 University St., Montréal, Québec H3A 2A7, Canada

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): 8, Downloads (12 Months): 21, Citation Count: 5

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/309831.309863 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	BOJANOV, D.. HAKOPIAN, H. A.: AND SAHAKIAN: A. A. Spline Functions and Multivariate InteTTolations. Kluwer Academic Publishers, 1993.
	3	Michael Clausen , Andreas Dress , Johannes Grabmeier , Marek Karpinski, On zero-testing and interpolation of k -sparse multivariate polynomials over finite fields, Theoretical Computer Science, v.84 n.2, p.151-164, July 29, 1991 [doi>10.1016/0304-3975(91)90157-W]
	4	DE BOOR, C.. AND RON, A. Computational aspects of polynomial i~terpolation in several vaa'iables. Mathematics of Computation 58 (1992), 705-727.
	5	A. Dür , J. Grabmeier, Applying coding theory to sparse interpolation, SIAM Journal on Computing, v.22 n.4, p.695-704, Aug. 1993 [doi>10.1137/0222046]
	6	GOLDREICII, O.., I~.UBINFELD. 1:{.., AND SUDAN, M. Learning polynomials with queries" The highly noisy case. Report, Electronic Colloqium on Computational Complexity, August 1998.
	7	GURUSWAMI, V., AND SUDAN, M. hnproved decoding of reed-solomon and algebraic-geometric codes. In Symposium on Discrete Algorithms (Palo Alto, California, November, 1998), ACM-SIAM, pp. 108 117.
	8	Ming-Deh A. Huang , Ashwin J. Rao, Interpolation of sparse multivariate polynomials over large finite fields with applications, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.508-517, January 28-30, 1996, Atlanta, Georgia, United States
	9	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	10	Ron M. Roth , Gyora M. Benedek, Interpolation and approximation of sparse multivariate polynomials over GF(2), SIAM Journal on Computing, v.20 n.2, p.291-314, April 1990 [doi>10.1137/0220019]
	11	SAUER, T. Polynomial interpolation of minimal degree. Numerische Mathematik Manuscript (to appear in1996).
	12	Zeljko Zilic , Zvonko G. Vranesic, Towards spectral synthesis: field expansions for partial functions and logic modules for fgpas, 1997
	13	Zvonko G. Vranesic , Zeljko Zilic, A Multiple-Valued Reed-Muller Transform for Incompletely Specified Functions, IEEE Transactions on Computers, v.44 n.8, p.1012-1020, August 1995 [doi>10.1109/12.403717]
	14	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]
	15	ZIPPEL, R. Effective Polynomial Computation. Kluwer Academic Publishers, 1993.

CITED BY 5

	Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland
	Katarzyna Radecka , Zeljko Zilic, Specifying and verifying imprecise sequential datapaths by Arithmetic Transforms, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.128-131, November 10-14, 2002, San Jose, California
	Erich Kaltofen , Wen-shin Lee, Early termination in sparse interpolation algorithms, Journal of Symbolic Computation, v.36 n.3-4, p.365-400, September 2003
	Mark Giesbrecht , George Labahn , Wen-shin Lee, Symbolic-numeric sparse interpolation of multivariate polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Mark Giesbrecht , George Labahn , Wen-shin Lee, Symbolic-numeric sparse interpolation of multivariate polynomials, Journal of Symbolic Computation, v.44 n.8, p.943-959, August, 2009