# Extracting coefficients of polynomials given by straight line programs

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.

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$$.

• Thank you, that’s perfect! And good reminder that if I think there’s a vague connection to both SETH and (separately) subset sum per @Mahdi’s answer, the search for “seth subset sum” is obligatory. Apr 9, 2022 at 14:25

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.

• It seems like that rules out $\log^{O(1)} n$ algorithms, but why does it rule out $O(n^\theta)$ algorithms with $\theta < 1$? Apr 8, 2022 at 7:57

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-$$ 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.

• Does this hardness result say anything about whether $O(n^\theta)$ algorithms exist for $\theta < 1$ (which was the formulation of the question)? Your reduction to univariate blows up degree in a way that seems to break $n^\theta$. Apr 8, 2022 at 9:23
• Your comment seems right indeed. Apr 22, 2022 at 16:16