Extracting coefficients of polynomials given by straight line programs

Question

Consider a straight line program of length $L$ that takes one input $x \in \mathbb{R}$ and computes a polynomial $p(x)$, using only addition, multiplication (including multiplication by constants). We allow the degree to be very large: potentially $2^{\Theta(L)}$.

Question: Is there an $O(\operatorname{poly}(L)n^\theta)$ algorithm for computing the $n$th coefficient of $p(x)$, with $\theta < 1$?

I roughly want to say "assume exact arithmetic", but there is a subtlety in that sufficiently large exact arithmetic might allow cheating. It's possible Blum-Shub-Smale (BSS) is the right model, but I am not confident.

My guess is that the answer is (sadly) no, since all the straight line program polynomial algorithms I can find either (1) are linear or superlinear in degree or (2) assume $p(x)$ is sparse.

More details: I should add why I think $O(L^{O(1)} n^\theta)$ is the most interesting complexity goal, and unfortunately why I think it’s unobtainable. First, direct evaluation of all coefficients using FFT multiplication gives $O(L n \log n)$, so the goal is a slight reduction in the exponent of $n$. Ignoring dependence on $L$, this is achievable: there are baby step/giant step methods which achieve $O(n^{1/2})$ for any holonomic sequence (Bostan and Yurkevich 2020) is a nice example). However, the complexity of the holonomic recurrence grows badly with $L$, and I believe the total complexity is $2^{O(2^L)}n^{1/2}$. So the question is asking whether one can reduce the exponent on $n$ without blowing up the dependence on $L$.

Unfortunately, my best guess is that this is impossible, and specifically that it would contradict SETH. I don’t know how to do that reduction without losing precision on $\theta$, however.

Answer 1

This would contradict SETH by using a known hardness result for subset sum: https://arxiv.org/abs/1704.04546.

In this paper it is shown that the subset sum problem with $n$ integers and target $T$ cannot be solved in $T^{1-\varepsilon} \cdot 2^{o(n)}$ time for any $\varepsilon>0$. What you propose would give a $T^\theta \cdot n^{O(1)}$ algorithm as follows:

Let the input numbers be $a_1, \ldots, a_n$. For each $a_i$, we can construct a straight line program that computes the polynomial $x^{a_i} + 1$ and has length $O(\log a_i)$. Then by multiplying these together, we get a straight line program of length linear in the number of bits of the input with the property that the $T$:th coefficient is nonzero if and only if there is some subset that sums to $T$.

Answer 2

You can easily encode #P problems such as the number of solutions to a subset-sum instance as coefficients of a generating polynomial, so the answer is likely not.

Answer 3

It seems that there exists a hardness result: If $f$ is a (multivariate) polynomial computed by an arithmetic circuit (that is a SLP), it is $\mathsf P^{\#\mathsf P}$-hard to test whether the coefficient of a given monomial equals zero [1]. I think this translates to your univariate settings by standard Kronecker substitution (replacing a $k$-variate degree-$<D$ polynomial $f$ by the univariate $f(x,x^D,…,x^{D^{k-1}})$).

[1] Koiran, Perifel. The complexity of two problems on arithmetic circuits, TCS 389(1-2), pp 172-181, 2007, doi:10.1016/j.tcs.2007.08.008.