# Questions tagged [polynomials]

The tag has no usage guidance.

130 questions
Filter by
Sorted by
Tagged with
1 vote
66 views

### Subquadratic multiplication of polynomials in the max-plus/tropical semiring

Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $(\mathbb{Z}\cup\{-\infty\}, \max, +)$ which is faster than the trivial one? I'm interested in the ...
99 views

### NP-hardness of solving systems of *homogeneous* polynomial equations

It is well-known that deciding if a system of quadratic polynomial equations in several variables admits a solution in a finite field is NP-complete. There is a simple reduction from 3SAT, that works ...
1 vote
34 views

4k views

### What is the most efficient algorithm to compute polynomial coefficients from its roots?

Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is $$y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$$ To get the coefficients, i.e., $y = \sum_{i}^n a_i x^i$, a ...
42 views

### From roots to coefficients of a polynomial [duplicate]

Polynomials are usually written as a sum of powers (or various products of generators) and Google gives me lots of results on how to get from that to the form that is a product of degree-$1$ ...
22 views

### Given x find a polynomial such that pol(x)=a for a known a?

You are given x,a. Find a polynomial p(y) with the leading coafficent 1 such that p(x)=a. How to write an algorithem to solve this efficently? I have no idea where to start
1 vote
62 views

### Finding points of local maximum error in Remez algorithm

So the Remez algorithm is an algorithm for finding optimal polynomial approximations or at the very least for converging towards them. To find an approximation of $f$ by an $N$th degree polynomial the ...
198 views

### Computing coefficients of $p(x)^n$ in time $O(n \log n)$

For homework I've to give an algorithm that computes the coefficients of the polynomial $p(x)^n$ in time $O(n\log n)$, where $p(x)$ is a polynomial of degree 7. As an hint I'm told to consider first ...
53 views

120 views

### Decide whether a polynomial has a root

Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is ...
1 vote
66 views

### Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n

Here is a question from Computational Complexity by Arora and Barak: Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$. (...
1 vote
37 views

233 views

### Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?

In the book 'Computational Complexity' by Arora and Barak the following question is posed (exercise 2.20.): Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real ...
I need to find the first $n$ coefficients of $$\prod_{i = 1}^{i = q}(1 + x^{a_i})^{b_i}$$ modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity $O(n\log n)$ or \$O(...