<p>This would contradict SETH by using a known hardness result for subset sum: <a href="https://arxiv.org/abs/1704.04546" rel="nofollow noreferrer">https://arxiv.org/abs/1704.04546</a>.</p>
<p>In this paper it is shown that the subset sum problem with <span class="math-container">$n$</span> integers and target <span class="math-container">$T$</span> cannot be solved in <span class="math-container">$T^{1-\varepsilon} \cdot 2^{o(n)}$</span> time for any <span class="math-container">$\varepsilon&gt;0$</span>. What you propose would give a <span class="math-container">$T^\theta \cdot n^{O(1)}$</span> algorithm as follows:</p>
<p>Let the input numbers be <span class="math-container">$a_1, \ldots, a_n$</span>. For each <span class="math-container">$a_i$</span>, we can construct a straight line program that computes the polynomial <span class="math-container">$x^{a_i} + 1$</span> and has length <span class="math-container">$O(\log a_i)$</span>. 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 <span class="math-container">$T$</span>:th coefficient is nonzero if and only if there is some subset that sums to <span class="math-container">$T$</span>.</p>

CC BY-SA 4.0
2022-04-09T14:25:51.353Z
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.
Geoffrey Irving
CC BY-SA 4.0
2022-04-09T13:13:10.770Z
2022-04-09T13:29:14.890Z
2022-04-09T13:29:14.890Z
Laakeri
<p>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.</p>

CC BY-SA 4.0
2022-04-08T07:57:50.087Z
It seems like that rules out $\log^{O(1)} n$ algorithms, but why does it rule out $O(n^\theta)$ algorithms with $\theta < 1$?
Geoffrey Irving
CC BY-SA 4.0
2022-04-08T00:07:23.733Z
2022-04-08T00:07:23.733Z
Mahdi Cheraghchi
<p>It seems that there exists a hardness result: If <span class="math-container">$f$</span> is a (multivariate) polynomial computed by an arithmetic circuit (that is a SLP), it is <span class="math-container">$\mathsf P^{\#\mathsf P}$</span>-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 <span class="math-container">$k$</span>-variate degree-<span class="math-container">$&lt;D$</span> polynomial <span class="math-container">$f$</span> by the univariate <span class="math-container">$f(x,x^D,…,x^{D^{k-1}})$</span>).</p>
<p>[1] Koiran, Perifel. <em>The complexity of two problems on arithmetic circuits</em>, TCS 389(1-2), pp 172-181, 2007, doi:<a href="https://doi.org/10.1016/j.tcs.2007.08.008" rel="nofollow noreferrer">10.1016/j.tcs.2007.08.008</a>.</p>

CC BY-SA 4.0
2022-04-08T09:23:14.073Z
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$.
Geoffrey Irving
CC BY-SA 4.0
2022-04-22T16:16:44.140Z
Your comment seems right indeed.
Bruno
CC BY-SA 4.0
2022-04-08T09:06:20.423Z
2022-04-08T09:06:20.423Z
Bruno
<p>Consider a straight line program of length <span class="math-container">$L$</span> that takes one input <span class="math-container">$x \in \mathbb{R}$</span> and computes a polynomial <span class="math-container">$p(x)$</span>, using only addition, multiplication (including multiplication by constants).  We allow the degree to be very large: potentially <span class="math-container">$2^{\Theta(L)}$</span>.</p>
<p><strong>Question:</strong> Is there an <span class="math-container">$O(\operatorname{poly}(L)n^\theta)$</span> algorithm for computing the <span class="math-container">$n$</span>th coefficient of <span class="math-container">$p(x)$</span>, with <span class="math-container">$\theta &lt; 1$</span>?</p>
<p>I roughly want to say &quot;assume exact arithmetic&quot;, but there is a subtlety in that sufficiently large exact arithmetic might allow cheating.  It's possible <a href="https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow noreferrer">Blum-Shub-Smale (BSS)</a> is the right model, but I am not confident.</p>
<p>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 <span class="math-container">$p(x)$</span> is sparse.</p>
<p><strong>More details:</strong> I should add why I think <span class="math-container">$O(L^{O(1)} n^\theta)$</span> is the most interesting complexity goal, and unfortunately why I think it’s unobtainable.  First, direct evaluation of all coefficients using FFT multiplication gives <span class="math-container">$O(L n \log n)$</span>, so the goal is a slight reduction in the exponent of <span class="math-container">$n$</span>.  Ignoring dependence on <span class="math-container">$L$</span>, this is achievable: there are baby step/giant step methods which achieve <span class="math-container">$O(n^{1/2})$</span> for any holonomic sequence (<a href="https://arxiv.org/abs/2012.08656" rel="nofollow noreferrer">Bostan and Yurkevich 2020</a>) is a nice example).  However, the complexity of the holonomic recurrence grows badly with <span class="math-container">$L$</span>, and I believe the total complexity is <span class="math-container">$2^{O(2^L)}n^{1/2}$</span>. So the question is asking whether one can  reduce the exponent on <span class="math-container">$n$</span> without blowing up the dependence on <span class="math-container">$L$</span>.</p>
<p>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 <span class="math-container">$\theta$</span>, however.</p>

<polynomials>
Extracting coefficients of polynomials given by straight line programs
Geoffrey Irving
# Extracting coefficients of polynomials given by straight line programs

(Asked by: username_0 on 2022-04-06)

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)](https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine) 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](https://arxiv.org/abs/2012.08656)) 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.

**Tags:** polynomials


---

## 3 answers

### Answer by username_1 on 2022-04-09. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2022-04-08. Score: 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.

> **Comments:**
> **username_0**: It seems like that rules out $\log^{O(1)} n$ algorithms, but why does it rule out $O(n^\theta)$ algorithms with $\theta < 1$?  

---

### Answer by username_3 on 2022-04-08. Score: 1

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](https://doi.org/10.1016/j.tcs.2007.08.008).

> **Comments:**
> **username_0**: 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$.  
> **username_3**: Your comment seems right indeed.  

---

