Questions tagged [polynomials]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
user93353's user avatar
  • 125
2 votes
0 answers
122 views

Optimal reassociations is NP-hard?

Consider signed integers with common addition and multiplication. Reassociation of expression is another equivalent form. Say expressions: ...
Konstantin Vladimirov's user avatar
0 votes
1 answer
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 ...
Kong's user avatar
  • 1
0 votes
0 answers
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 ...
Colonizor48's user avatar
0 votes
2 answers
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 ...
meeeeee's user avatar
1 vote
1 answer
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 ...
bihariforces's user avatar
2 votes
0 answers
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 ...
Mathdropout's user avatar
1 vote
1 answer
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 ...
ant_arctic's user avatar
0 votes
1 answer
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 ...
R.Jean's user avatar
  • 3
0 votes
1 answer
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 ...
Matt Samuel's user avatar
1 vote
0 answers
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 ...
Rohit Pandey's user avatar
0 votes
1 answer
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 ...
Thorkil Værge's user avatar
2 votes
0 answers
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 ...
Mathdropout's user avatar
1 vote
1 answer
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$...
GBathie's user avatar
  • 632
1 vote
0 answers
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 ...
Miquel Ramirez's user avatar
1 vote
0 answers
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)$ ...
Somnium's user avatar
  • 275
4 votes
0 answers
53 views

Polynomial multiplication in finite field without smooth-order roots of unity

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 ...
Mathdropout's user avatar
2 votes
3 answers
563 views

Deciding whether an integer polynomial has an integer root

This is a question written by my instructor Z. Loria . Consider the following problem: Given a polynomial $p(x) = \sum_{i=0}^n a_ix^i$, where $a_i$ are integers, is there a natural number $n \in \...
RedYoel's user avatar
  • 217
1 vote
1 answer
104 views

Does the reliability of polynomial hashing depend on whether the modulus is prime, for coprime base and modulus?

A polynomial hash of a string $s$ with base $b$ and modulus $M$ is defined as $$ H(s) = (s_0 + s_1 b + s_2 b^2 + \dots + s_{n-1} b^{n-1}) \mod M. $$ I have proven (and this is quite obvious) that ...
Alisa Sireneva's user avatar
2 votes
1 answer
50 views

Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?

I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
David Jentjens's user avatar
1 vote
0 answers
42 views

Efficient bit-level implementation of Boolean polynomials with few variables

A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form $$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$...
BubbleZ's user avatar
  • 11
0 votes
0 answers
40 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$ ...
John's user avatar
  • 121
0 votes
1 answer
126 views

Finding $Aeven(x)$ and $Aodd(x)$ for a Fast Fourier Transform (FFT) problem?

In this article about FFT the author used FFT on this polynomial. $A(x) = 3+2x+3x^2+4x^3$ Using $ A(x)= Aeven(x^2) + xAodd(x^2)$ the author determined the following for $Aeven(x)$ and $Aodd(x)$ $ ...
calico jack's user avatar
-1 votes
1 answer
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
sean python's user avatar
1 vote
0 answers
59 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 ...
Jake's user avatar
  • 3,790
3 votes
1 answer
177 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 ...
RedYoel's user avatar
  • 217
0 votes
0 answers
52 views

Time to evaluate a product of binomials $1 + x^i$

I am considering the asymptotic analysis required to convert a polynomial of the shape $$P(x) = \prod_{i = 1}^{n}(1 + x^{s_i})$$ to its "full" representation, for example $$P(x) = 1+x^3+x^5+...
Mikkel Andersen's user avatar
0 votes
1 answer
189 views

Multiplication of polynomials in value representation as done for Fast Fourier Transform

I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the ...
heretoinfinity's user avatar
1 vote
0 answers
91 views

Optimize binary multivariate polynomial multiplication

You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the ...
Victor Marcelino's user avatar
1 vote
1 answer
73 views

How polynomial interpolation of polynomial multiplication algorithm works?

I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following: Algorithm [DPV, p. 60] Input: Coefficients of two polynomials. ...
user777's user avatar
  • 729
1 vote
0 answers
67 views

Express polynomial as sum of two lower-degree polynomials, modulo another

Suppose I have a polynomial $p(x)$, and a "modulus" polynomial $q(x)$ of degree $d$. I want to find two polynomials $r_1(x),r_2(x)$ of degree $\le d_1,d_2$ such that $$p(x) \equiv r_1(x) x^...
D.W.'s user avatar
  • 156k
2 votes
0 answers
112 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 ...
Rémi's user avatar
  • 86
1 vote
2 answers
64 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$. (...
roydiptajit's user avatar
1 vote
0 answers
29 views

Binomial basis and the usual basis of polynomial algebra $\mathbb C(X)$

Consider the polynomial algebra $\mathbb C[X]$. Then the set $\{1, X, X^2,\dots,\}$ forms a vector space basis for this algebra. In general, we know that the set $\{P_n(X) \in \mathbb C[X]: n \ge 0 \...
GA316's user avatar
  • 111
0 votes
1 answer
48 views

Represent a DNF formula as a multivariate linear formula?

Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$ How do I convert that into a polynomial form?
Michael's user avatar
1 vote
0 answers
43 views

How do I decode a received polynomial code with an error?

As a message I get (5,0,1,3), which is coding a sequence of numbers of length 2 in $\mathbb{F}_7$ as polynom with the 4 support points a1 = 0, a2 = 1, a3 = 2, a4 = 6. In the transimission occured an ...
Rapiz's user avatar
  • 21
1 vote
1 answer
190 views

Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$

Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$. For eg. Let the array be $1,2,3$ then my answer will be calculated as- $(2-1)$.$(...
Viplaw Srivastava's user avatar
2 votes
0 answers
175 views

Understanding CRC Computation with PCLMULQDQ

I am currently reading this paper which shows how to calculate CRC using the instruction PCLMULQDQ. I don't quite understand the equations in it yet. Starting with this one for the definition of ...
Paul Schaaf's user avatar
3 votes
1 answer
196 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 ...
mwien's user avatar
  • 33
1 vote
0 answers
62 views

How to compute the first n coefficients using number theoretic transform (NTT)?

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(...
Nick Ger's user avatar
2 votes
1 answer
184 views

Why does $x^{15}+x^{14}+1$ detect all errors at most 32768 bits apart?

Reference Question from Forouzon Book Computer Network. Find the status of the following generator related to two isolated, single-bit errors. $$x^{15} + x^{14} + 1$$ Answer given : This polynomial ...
Piyush Sawarkar's user avatar
3 votes
0 answers
29 views

Bit complexity of computing the sign of an expression evaluated at an algebraic number

I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
asdf's user avatar
  • 131
3 votes
1 answer
378 views

Is O(n log n) exponential speedup over O(n^2)?

I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?
Rascalniikov's user avatar
0 votes
0 answers
265 views

Multiplying bivariate polynomials using FFT

Consider two bivariate polynomials of degree at most $n-1$ in each variable: $$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^i y^j \quad \text{and} \quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^i y^j. $$ ...
lan's user avatar
  • 1
15 votes
2 answers
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 ...
xucheng's user avatar
  • 253
2 votes
1 answer
228 views

Polynomial multiplications and counting

I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically ...
Narek Bojikian's user avatar
1 vote
1 answer
319 views

Fitting a polynomial to a set of points or to a skeleton

Available data Available to me is a set of points which can be represented as shown in image 1: Also available to me is a non-continuous path derived from this data. It is not important how this non-...
Koenigsberg's user avatar
1 vote
0 answers
35 views

Generating a set of divergence-free basis

I'm trying to derive an algorithm that would generate a set of divergence-free vectors, which shall be used as basis vectors later on. Using a simple example, a 2D second-order divergence-free basis ...
Quang Thinh Ha's user avatar
2 votes
1 answer
88 views

Polynomials - using Newton's method, or not?

I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed. I can use general Newton's ...
Bojan Vukasovic's user avatar
3 votes
1 answer
104 views

Polynomial size Boolean circuit for counting number of bits

Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
Noel Arteche's user avatar