5
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Apr 9, 2022 at 14:25
2
$\begingroup$

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.

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

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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$. $\endgroup$ Apr 8, 2022 at 9:23
  • 1
    $\begingroup$ Your comment seems right indeed. $\endgroup$
    – Bruno
    Apr 22, 2022 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.