I am trying to compute a monic polynomial $f(x)$ with integer coefficients and known degree $d$. I am given $n$ pairwise coprime polynomials $g_1(x),\ldots,g_n(x)$, also with integer coefficients, each monic of degree at most $e < d$. I am also given the values of the $n$ resultants $\mathrm{Res}_x(f(x),g_i(x))$ for $i = 1,\ldots,n$.

The question is: find an algorithm that recovers $f(x)$ from these inputs, for some value of $n$ (depending on $d$ and $e$).

If I take $n = (d+1)$ choose $e$, then an algorithm is as follows: write the coefficients of $f$ as indeterminates, and write out each resultant in terms of these variables. Then I get $n$ polynomial equations in $d$ variables of degree at most $e$. I linearize the system, and if $n$ is as above then I have enough equations to find a solution.

I suspect there is some algorithm involving Gröbner bases, but I doubt it is any faster than the above.

Ideally I would like an algorithm that is polynomial-time in $d$ and $e$. (In my application I have $e = O(\sqrt{d})$.) I have no idea if such an algorithm is reasonable to expect. Even something better than $O(d^e)$ would be nice.

[EDIT] What gives me hope are these two papers:

C. Hillar, Cyclic Resultants, Journal of Symbolic Computation, 39 (2005), 653-669.

C. Hillar and L. Levine, Polynomial recurrences and cyclic resultants, Proceedings of the American Mathematical Society, 135 (2007), 1607-1618.

They show that if $g_i(x) = x^i - 1$ then there is an algorithm. The algorithm requires exponentially many resultants, but they conjecture that it is possible with polynomially many. I was hoping that if we allow a larger set of $g_i$ but strongly constrain the degrees than we can still recover something.