On the decidability of sparse univariate polynomial interpolation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the decidability of sparse univariate polynomial interpolation

Full text

Pdf (806 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 535 - 545

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

A. Borodin	Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
P. Tiwari	Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/100216.100292 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	[BT89] A. Borodin and P. Tiwari. On the decidability of sparse univariate polynomial interpolation. IBM Research Report RC 14923, 27 pages, September 1989.
	2	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]
	3	[BSS88] L. Blum and M. Shub and S. Smale. On a theory of computation over the real number; NP completeness, recursive functions and universal machines. Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, 387- 397, 1988.
	4	[EI76] R. J. Evans and I. M. Isaacs. Generalized Vandermonde determinants and roots of unity of prime order. Proceedings of the American Mathematical Society 58:51- 54, 1976.
	5	[Ga59] F. R. Gantmacher. The Theory of Matrices . K. A. Hirsch, New York, 1959.
	6	[GK87] D. Yu. Grigoriev and M. Karpinski. The matching problem for bipartite graphs with polynomially bounded permanents is in NC. Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 166-172, 1987.
	7	[J74] N. Jacobson. Basic Algebra I. W. H. Freeman and Company, San Francisco, 1974.
	8	[KW89] M. Karpinski and T. Werther. Learnability and VC-dimension of sparse polynomials and rational functions. In preparation.
	9	[MM64] M. Marcus and H. Minc. Basic Algebra A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, Boston, Mass., 1964.
	10	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	11	[T87] P. Tiwari. Parallel algorithms for instances of linear matroid parity with a small number of solutions. IBM Research Report 12766. IBM T. J. Watson Research Center, New York, 1987.
	12	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

CITED BY 4

	Marek Karpinski , Angus Macintyre, Polynomial bounds for VC dimension of sigmoidal neural networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.200-208, May 29-June 01, 1995, Las Vegas, Nevada, United States
	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
	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning arithmetic read-once formulas, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.370-381, May 04-06, 1992, Victoria, British Columbia, 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