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 ...
- 270k
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.♦
- 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 ...
D.W.♦
- 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 ...
- 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^{...
- 270k
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 ...
- 270k
5
votes
Accepted
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$...
- 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$,...
- 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 ...
- 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....
- 51
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})$).
...
- 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, ...
- 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 ...
- 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 ...
D.W.♦
- 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 ...
- 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.
- 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 ...
- 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....
D.W.♦
- 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 ...
- 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 ...
- 270k
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 ...
- 80.4k
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 &...
- 270k
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^{...
- 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} ...
- 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 ...
- 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(...
- 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 ...
- 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$. ...
- 34.9k
Only top scored, non community-wiki answers of a minimum length are eligible