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 ...
Yuval Filmus's 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_{...
D.W.'s user avatar
  • 158k
14 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 ...
D.W.'s user avatar
  • 158k
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^{...
Yuval Filmus's 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 ...
Yuval Filmus's 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})$). ...
jschnei's user avatar
  • 364
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....
user95902's user avatar
5 votes
Accepted

Converting Polynomials into Binary form

Just put the value of $x=10$ then $$10^3+1=1001$$
Harsh Kumar's user avatar
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, ...
Pseudonym's user avatar
  • 22k
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 ...
John L.'s user avatar
  • 38.8k
4 votes
Accepted

Meaning of polynomially larger or smaller in the context of the master method

(This answer refers to the version 6 of the question, which does not contain "my professor's response".) It looks like there is some typo/inconsistency/misunderstanding somewhere in your ...
John L.'s user avatar
  • 38.8k
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.
nir shahar's user avatar
  • 11.5k
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 ...
Caleb Stanford's user avatar
4 votes
Accepted

Complexity of multiplying bivariate polynomials of degree n

It suffices to describe how to evaluate $P(\omega^u,\omega^v)$ at the roots of unity. Suppose $P(X,Y)=\sum_{i,j} a_{i,j} X^i Y^j$. Let $$F_{b,c}(X,Y) = \sum_{i,j} a_{2i+b,2j+c} X^i Y^j$$ where the ...
D.W.'s user avatar
  • 158k
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....
D.W.'s user avatar
  • 158k
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(...
gnasher729's user avatar
  • 29.4k
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 ...
gnasher729's user avatar
  • 29.4k
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} ...
Peter Taylor's user avatar
  • 2,082
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^{...
fade2black's user avatar
  • 9,817
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 ...
Yuval Filmus's user avatar
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 ...
Bulat's user avatar
  • 1,853
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$. ...
John L.'s user avatar
  • 38.8k
3 votes
Accepted

How to find sets of polynomially bounded numbers whose subset sums are different?

There are many functions that satisfy your condition. Here are a few. $a_i=1+c^{-i}$, for some constant $c\ge 2$. $a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer ...
John L.'s user avatar
  • 38.8k
3 votes

Decidability of factoring algebraic equations

Interesting question. Factorization of functions, including factorization of polynomials is in fact a classical problem throughout history of mathematics. For the sake of contradiction, assume that ...
John L.'s user avatar
  • 38.8k
3 votes

Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?

Multiplying a degree $d$ polynomial by a degree $1$ monic polynomial requires $d$ multiplications (and some additions). This can be seen from the following formula: $$ (x-c) \sum_{i=0}^d b_i x^i = (-...
Yuval Filmus's user avatar
3 votes

Polylogarithm growth rate proof using Polynomial growth equation

Here is the starting point. For all real constants $a$ and $b$ such that $a > 1$, $$\lim_{n\to\infty}\frac{n^b}{a^n} = 0\,.\tag{3.10}$$ Let $c=\log_2 a$, i.e, $a=2^c$. Since $a>1$, we have $c&...
John L.'s user avatar
  • 38.8k
3 votes
Accepted

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

Suppose $n = 2^k$ and for $0\leq i \leq k$, set $p_i(x) = p(x)^{2^i}$. We want to efficiently compute $p_k(x)$. It is clear that for $0\leq i < k$, $p_{i+1}(x) = p_i(x)^2$. Using the Cooley-Tukey ...
Nathaniel's user avatar
  • 13.9k
3 votes

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

With some manipulations: $$ f(n) = 4^{n^2 \log n} = (2^2)^{n^2 \log n} = (2^{\log n})^{2n^2} = n^{2 n^2}. $$ and: $$ g(n)= (n!)^n \le (n^n)^n = n^{n^2}. $$ Taking the limit: $$ \lim_{n \to \infty} \...
Steven's user avatar
  • 29.4k
2 votes

Find all rational roots of a polynomial equation

If you only want to find all rational roots, you can simply use the rational root theorem. This theorem states that, given a polynomial $a_n x^n + a_{n-1}x^{n-1} + \ldots + a_1x+a_0$, for any rational ...
Discrete lizard's user avatar
  • 8,128
2 votes

Find all rational roots of a polynomial equation

The paper Computing Real Roots of Real Polynomials by Sagraloff and Mehlhorn from 2015 provides an almost optimal algorithm and references for simpler algorithms that might be used in practice. The ...
adrianN's user avatar
  • 5,931

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