Federal Republic of Germany AND (2008)
Dima Yu. Grigoriev, Marek Karpinski, Michael F. Singer
In [DG 891, the authors show that many results concerning the problem of efficient interpolation of k-sparse multivariate polynomials can be formulated and proved in the general setting of k-sparse...
Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis (1996)
Dima Yu. Grigoriev, Marek Karpinski, Andrew M. Odlyzko
Symbolic manipulation of sparse polynomials, given as lists of exponents and nonzero coefficients, appears to be much more complicated than dealing with polynomials in dense encoding (see e.g. [GKS...
Algorithms for Sparse Rational Interpolation (1991)
Dima Yu. Grigoriev, Marek Karpinski
We present two algorithms on sparse rational interpolation. The first is the interpolation algorithm in a sense of sparse partial fraction representation of rational functions. The second is the...
Algorithms for Computing Sparse Shifts for Multivariate Polynomials
Dima Yu. Grigoriev, Y. N. Lakshman
In this paper, we investigate the problem of finding t-sparse shifts for multivariate polynomials. Given a polynomial f 2 F [x 1 ; x 2 ; : : : ; x n ] of degree d, and a positive integer t, we...