# Questions tagged [polynomials]

The tag has no usage guidance.

112 questions
Filter by
Sorted by
Tagged with
1 vote
34 views

### Complexity of multiplying bivariate polynomials of degree n

Let $P(X,Y)$ and $Q(X,Y)$ be two bivariate polynomials of degree at most $n$. Using $O(n^2)$ FFTs, we can compute the product $PQ$ in time $O(n^3\log n)$. Q: Is there a faster algorithm to compute $PQ$...
• 632
1 vote
17 views

### Time and Space Complexity of Isolating the Roots of a Polynomial

Can someone provide a list of references of papers, books, etc. presenting results on the time and space complexity of the problem of isolating the roots of a univariate polynomial $P(t)$ with integer ...
1 vote
81 views

### What's the fastest algorithm for polynomial interpolation in finite field with prime order at points 1, 2, 3, ..., n?

Suppose we have finite field $\mathbb{F}_p$ with prime order $p$. Can we find polynomial in $\mathbb{F}_p[x]$ having given values $a_1, a_2, ... a_n$ at $x=1, 2, ..., n$ in less than $O(n^2)$ ...
• 265
I am working in a finite prime field $\mathbb{F}_p$ that does not have primitive $n$-th roots of unity for any large smooth integer $n$, which makes FFTs a bit difficult. If I need to compute a ...