31 votes
Accepted

Find a polynomial in two or three queries

You can determine the polynomial using two queries. First query the polynomial at $x=1$ to get an upper bound $M$ on the value of the coefficients. Now query the polynomial at $x > M$ of your ...
user avatar
25 votes
Accepted

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

This can be done in $O(n \log^2 n)$ time, even if the $x_i$ have duplicates, via the following divide-and-conquer method. First compute the coefficients of the polynomial $f_0(x)=(x-x_1) \cdots (x-x_{...
user avatar
  • 143k
13 votes

Multi-point evaluations of a polynomial mod p

No, $O(n \lg q)$ running time is not achievable. It takes $\Omega(q)$ space even just to write out the answer, so any algorithm will necessarily have running time at least $\Omega(q)$. However, you ...
user avatar
  • 143k
6 votes
Accepted

BSS-model Computational complexity of finding the roots of a polyomial

It's not too hard to find the real roots of a univariate polynomial, for example by using Sturm's theorem which allows you to easily identify the number of sign changes of a real-valued polynomial ...
user avatar
  • 7,744
6 votes
Accepted

Check if a given polynomial is primitive

In order to check that a degree $n$ polynomial $P$ over $GF(2)$ is primitive, you first need to know the factorization of $2^n-1$ (you can look it up in tables, or use a CAS). Then, you test that $x^{...
user avatar
6 votes
Accepted

Efficient algorithm to translate/shift polynomials

Use FFT. Suppose that $\deg P \leq n$ and we use FFT on $n$ points (usually $n$ would be the smallest power of 2 which is at least $\deg P$). Let $\omega$ be an $n$th root of unity. The Fourier ...
user avatar
5 votes
Accepted

Converting Polynomials into Binary form

Just put the value of $x=10$ then $$10^3+1=1001$$
user avatar
5 votes

What is the use of Horner's Method?

Yes, exactly as you said. This is used to decrease the number of multiplications, so it is more efficient than computing it the normal way. Example: You have the polynomial $ax^3 + bx^2 + cx + d$...
user avatar
  • 9,325
5 votes

Calculating the number of multiplications necessary to evaluate a polynomial

I am not sure what the slide was intended for, so I just gave a straight answer to your question in a comment, viz that the slide really intended 3 multiplications for $4x^3=4\times x\times x\times x$,...
user avatar
  • 19.2k
5 votes
Accepted

Is there a complexity viewpoint of Galois' theorem?

Interesting connection, however Galois theory states that no (consistent) method exists for finding roots of quintic using radicals, instead of saying that the problem has a solution (eg a longest ...
user avatar
  • 929
5 votes

Converting Polynomials into Binary form

The polynomial notation is a shortcut to write binary code while omitting the zeros, it's useful to crunch CRC communication checksum to verify electric signal quality with an XOR comparison operation....
user avatar
5 votes
Accepted

Lower bound of degree of polynomial approximating parity

You can show a polynomial of degree $O(\sqrt{n\log n})$ can agree with parity on all but $o(1)$ fraction of the inputs. (In fact, this argument should work for anything of degree $\omega(\sqrt{n})$). ...
user avatar
  • 309
5 votes
Accepted

Deciding whether an integer polynomial has an integer root

(Let's call the root $\xi$, because $n$ here means the degree of the polynomial. That's seriously bugging me about the question.) The secret is in noticing that it's easy to test if $\xi$ is a root, ...
user avatar
  • 19.1k
4 votes

Multiplication of two or more algebraic quantities

Your algebraic quantities are polynomials in one variable. Multiplying two polynomials is an important computational problem with many applications. You can store a polynomial in two ways: store the ...
user avatar
  • 11.9k
4 votes

Fast polynomial calculation over $\mathbb{Z}_{487}$

You can very efficiently compute $a(x_j)$ for each of those 243 values of $x_j$ by simply evaluating $a(\cdot)$ using Horner's rule. The running time is 243 evaluations of $a(\cdot)$, and each ...
user avatar
  • 143k
4 votes

Last digit of polynomial value

Remainder modulo 10 instead of last digit What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10. For simplicity, we will compute the ...
user avatar
  • 34.9k
4 votes

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

Choose $$p(y):=y + (a-x)$$ $x$ and $a$ here are the constants you are given.
user avatar
  • 10.9k
4 votes
Accepted

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

The question in the title is subjective, but I suspect no. Hilbert's 10th is one of the most important, but also one of the most complex, results of the last century. The proof itself spans 21 years ...
user avatar
  • 5,214
3 votes
Accepted

How to find the symmetry group of a polynomial

There is a reduction from your problem to graph isomorphism, as explained in this question on Math Overflow. In particular, that answer shows how to obtain a random automorphism of the polynomial, i....
user avatar
  • 143k
3 votes

Is there a complexity viewpoint of Galois' theorem?

am going to take your questions as mostly open ended. the galois proof now known as the Abel-Ruffini thm shows the impossibility of polynomial solutions to the quintic. (in contrast to eg the ...
user avatar
  • 10.8k
3 votes
Accepted

Boolean function and real degree

Exercise 12 (online version) in §1 of Ryan O'Donnell's Analysis of Boolean functions shows that all Fourier coefficients of a degree $d$ function are integer multiples of $2^{-d}$. In particular, the ...
user avatar
3 votes

Calculating the number of multiplications necessary to evaluate a polynomial

Yes, there's an error on the slide: as you say, there are only four addition operations (count the plus signs!) and, e.g., computing $4x^3 = 4\times x\times x\times x$ requires only three ...
user avatar
3 votes
Accepted

Proof of Minsky Papert Symmetrization technique

Over $0/1$ inputs we have $$ \begin{align*} (y_1+\cdots+y_N)^0 &= 1 \\ (y_1+\cdots+y_N)^1 &= \sum_i y_i \\ (y_1+\cdots+y_N)^2 &= \sum_i y_i+2\sum_{i<j} y_iy_j \\ (y_1+\cdots+y_N)^3 &...
user avatar
3 votes

Approximate a smooth f(x,y) function with a polynomial function

Wikipedia: In statistics, polynomial regression is a form of regression analysis in which the relationship between the independent variable $x$ and the dependent variable $y$ is modelled as an $n^{...
user avatar
  • 9,632
3 votes

Necessity of convolution operations for product of two polynomials via brute force method

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} ...
user avatar
  • 2,072
3 votes
Accepted

Necessity of convolution operations for product of two polynomials via brute force method

Given two polynomials $P_n(x)$, $Q_n(x)$, you can obviously calculate the value $P_n(x) · Q_n(x)$ in $O(n)$ for every x. The document asks about calculating the coefficients, which is a very different ...
user avatar
  • 25.5k
3 votes
Accepted

How to solve a polynomial of the form y = ax^3 + bx^2 + cx + d using the incremental algorithm in computer graphics

You have f(x). Let g(x) = f(x+1) - f(x). Let h(x) = g(x+1) - g(x). Let k(x) = h(x+1) - h(x). It turns out that k(x) is a constant. Calculate f(x), g(x), h(x) and k(x) for x = 1. Then you calculate f(...
user avatar
  • 25.5k
3 votes

Complexity of polynomial interpolation

Fast polynomial interpolation and Fast polynomial evaluation are algorithms that seem to be discovered back in 1973. They allow to interpolate/evaluate polynomial at N arbitrary points as far as field ...
user avatar
  • 1,805
3 votes
Accepted

Calculating a polynomial's coefficients from its roots

For every integer $i$, $0\le i\le n$, let $$P_i(X) = (X-x_1)(X-x_2)\cdots(X-x_i)=a_{i,i}X^i+a_{i,i-1}X^{i-1}+\cdots+...+a_{i,0}$$ for some $a_{i,k}$, $0\le k\le i$. In particular, $a_{i,i}=1$. ...
user avatar
  • 34.9k

Only top scored, non community-wiki answers of a minimum length are eligible