On the decidability of sparse univariate polynomial interpolation. (English) Zbl 0774.68067
Summary: We consider the problem of determining whether or not there exists a sparse univariate polynomial that interpolates a given set \(S=\{(x_ i,y_ i)\}\) of points. Several important cases are resolved, e.g., the case when the \(x_ i\)’s are all positive rational numbers. But the general problem remains open.
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | M. Ben-Or and P. Tiwari, A deterministic algorithm for sparse multivariate polynomial interpolation,Proc. 20th Ann. ACM Symp. Theory of Computing, 301-309, 1988. |
| [2] | L. Blum, M. Shub and S. Smale, On a theory of computation over the real number; NP completeness, recursive functions and universal machines,Proc. 29th IEEE Symp. Foundations of Comp. Sci., 387-397, 1988. · Zbl 0691.68034 |
| [3] | A. Borodin and P. Tiwari, On the decidability of sparse univariate polynomial interpolation (preliminary version),Proc. 22nd Ann. ACM Symp. Theory of Computing, 535-545, 1990. |
| [4] | R. J. Evans andI. M. Isaacs, Generalized Vandermonde determinants and roots of unity of prime order,Proc. Amer. Math. Soc. 58 (1976), 51-54. · Zbl 0337.12006 · doi:10.1090/S0002-9939-1976-0412205-0 |
| [5] | F. R. Gantmacher,The Theory of Matrices, K. A. Hirsch, New York, 1959. · Zbl 0085.01001 |
| [6] | D. Yu. Grigoriev and M. Karpinski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC,Proc. 28th IEEE Symp. Foundations of Comp. Sci., 166-172, 1987. |
| [7] | N. Jacobson,Basic Algebra I, W. H. Freeman and Company, San Francisco, 1974. |
| [8] | M. Karpinski andT. Werther,Learnability and VC-dimension of sparse polynomials and rational functions, Technical Report TR-89060, International Computer Science Institute, Berkeley, 1989. · Zbl 0799.68158 |
| [9] | D. E. Littlewood,The Theory of Group Characters and Matrix Representations of Groups, Oxford, 1950. · Zbl 0038.16504 |
| [10] | M. Marcus andH. Minc,Basic Algebra, A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Boston, Mass., 1964. · Zbl 0126.02404 |
| [11] | J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities,J. Assoc. Comput. Mach. 27 (1980), 701-707. · Zbl 0452.68050 |
| [12] | 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. |
| [13] | R. Zippel, Probabilistic algorithms for sparse polynomials.Lecture Notes in Computer Science 72,Symbolic and Algebraic Computation, 216-226, Springer-Verlag, 1979. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
