# Questions tagged [polynomials]

The tag has no usage guidance.

125 questions
Filter by
Sorted by
Tagged with
42 views

### Sumcheck protocol - how are these 2 polynomials different?

I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf - "Proofs, Arguments, and Zero-Knowledge" He is describing the Sumcheck Protocol on ...
122 views

### Optimal reassociations is NP-hard?

Consider signed integers with common addition and multiplication. Reassociation of expression is another equivalent form. Say expressions: ...
34 views

### Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?

Which function grows faster: $$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$ Which is true? $f(n) = O(g(n))$ $g(n) = O(f(n))$ i.e., $f(n) = \Theta(g(n))$ none of the above? For lower values of ...
44 views

### Progress towards a Polynomial time factoring algorithm?

This is probably insignificant, but I was messing around with polynomials, and found out that, if we have a number, n = pq that we want to factor, if we expand (k+1)^n -k^n - 1, mod n, the first ...
57 views

### Polynomial representations of Boolean functions

The AND boolean function $AND(x)$ can be represented using the polynomial $P(x) = x_1x_2\cdots x_n$. I have a few questions: Is there a similar polynomial for the PARITY boolean function? Is there a ...
1 vote
42 views

### product of every difference

Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $10^9 + 7$ $$\prod_{i < j} (arr[j] - arr[i]) \% (10^9 + 7)$$ Best approach I can ...
53 views

### Algorithm to compute sum of quotient polynomials

Let $f(X)$ be a polynomial in $\mathbb{F}_p[X]$ for some prime $p$ (of size 256 bits) that is not necessarily FFT-friendly. Let $a_1,\cdots,a_n$, $b_1,\cdots, b_n$ be $\mathbb{F}_p$ elements. What is ...
1 vote
43 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 ...
64 views

### O(nlogn)-time complexity

Is there a $O(nlogn)$ time algorithm for computing $p(x)=\sum\limits_{i=0}^na_ix^i$ ? I think with the method below I get O(n), but I need O(nlogn) Hint: there's a way to calculate $x^i$ more ...
54 views

### Algorithm for determining an algebraic positivity property of a multivariate polynomial

I am considering multivariate polynomials with integer coefficients that can be expressed as sums of products of terms of the form $y_i-z_j$ for positive integers $i$ and $j$. I am trying to find an ...
1 vote
46 views

### What algorithms apart from FFT get a computational boost by leveraging complex numbers?

If we think of the algorithmic problem of doing a convolution of two arrays, it turns out that converting them to the frequency domain first and then doing an element-wise product is equivalent. And ...
47 views

### Can an arithmetic circuit have multiple outputs?

An arithmetic circuit relates to calculating the value of a polynomial given some inputs. But is it still considered a circuit if the DAG corresponds to the evaluation of multiple polynomials that ...
66 views

### Fastest algorithm for polynomial multiplication in 256-bit finite fields

I am looking for the fastest algorithm (in practice) to multiply two polynomials $f(X)\cdot h(X)$ in $\mathbb{F}_p[X]$. The prime $p$ is roughly $256$ bits but the integer $p-1$ might not have any ...
1 vote
61 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$...
1 vote
23 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
111 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)$ ...
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 ...