30
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 choice and read off the coefficients from the base $x$ expansion.
Curiously, if you allow the coefficients to be negative then you cannot do better than $d$ queries....
22
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_{n/2})$ (via a recursive call to this algorithm). Then compute the coefficients of the polynomial $f_1(x)=(x-x_{n/2+1})\cdots(x-x_n)$. Next, compute the ...
9
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 can find algorithms that are more efficient than the naive solution. The naive solution for evaluating a polynomial of degree $n$ at $q$ points takes $O(nq)$ ...
6
The Galois field $GF(2^{128})$ has many different "concrete" representations. One popular representation is using polynomials in $GF(2)[x]$ (i.e. with coefficients in $GF(2)$) modulo some irreducible polynomial of degree $128$, say $x^{128}+x^7+x^2+x^1+x^0$. The magic constants $7,2,1,0$ come from this particular irreducible polynomial. You don't see $0$ ...
6
Let's assume that the numbers $a_1,\ldots,a_n$ are integers, so that the problem is in NP for any fixed $f$. We construct a polynomial $f$ so that the problem is NP-complete, by reduction from vertex cover in cubic graphs ($3$-regular graphs).
Let the instance of cubic vertex cover consist of a cubic graph $G=(V,E)$ and an integer $m$, and let $|V| = n$. ...
6
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 between two given bounds.
I believe it's not too hard to show that this technique, coupled with a simple divide-and-conquer technique or Newton's method and an ...
5
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 path) which may require super-polynomial time. So i would say it is more related to undecidability rather than complexity.
Specificaly, in Galois theory one ...
5
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$.
Computing directly you have six multiplications: (a * x * x * x, b * x * x, c * x). With Horner $((ax + b)x + c)x + d$ you have three multiplications: (a * ...
5
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$, and 4 additions to add the five terms.
Now of course, there are better ways to do that. Various powers of $x$
can be obtained in multiplying other powers of $...
5
It works if the denominator doesn't have negative coefficients. Consider, however,
$$ \frac{x}{x-1}. $$
As $x$ tends to infinity, this is $O(1)$. However, your method would give
$$ \frac{x}{x-1} = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-1} = \infty, $$
which is not very helpful. The problem is that when $x = 1$, the denominator is not positive. In this case ...
5
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})$).
Let $S = x_1 + x_2 + \dots + x_n$. Note that $\text{MOD}_2(x_1, x_2, \dots, x_n)$ can be written as a single-variable function of $S$. By Lagrange ...
4
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 coefficients, that is for $p(x)=3x^2-x+3$ you store $(3,-1,3)$
store enough samples, that is for $p(x)=3x^2-x+3$ you might store three values like $p(0)=3,p(1)=...
4
Remember that $O(-)$ is just an upper bound.
Given a rational function $p(x)/q(x)$, you already know how to find $c$, $k$ and $x_0$ such that $|p(x)|\leq c|x^k|$ for $x>x_0$. By similar arguments, you can show that $|q(x)|\ge 1$ for all $x$ greater than some $x_1$. Therefore, for all $x>\max\{x_0,x_1\}$, we have $|p(x)/q(x)| \leq |p(x)| \leq c|x^...
4
"Brute-force" in the context of factoring polynomials may involve factoring of integers, which is a hard problem. Factoring polynomials is easier, e.g. look up "FACTORING MULTIVARIATE POLYNOMIALS VIA PARTIAL DIFFERENTIAL EQUATIONS" by Gao, and "Factoring Multivariate polynomials over the integers" by Wang and Rothschild.
4
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 evaluation requires 243 modular multiplications and 243 modular additions. That's a total of $243^2 \approx 2^{16}$ modular multiplications. Consequently, the total ...
4
For completeness, I'll flesh out Yuval's answer a bit more through an example of multiplication of two polynomials $A$ and $B$ in $\text{GF}(2^{16})$. Let
$$A = [0001|1100|1110] = x^8 + x^7 + x^6 + x^3 + x^2 + x,$$ and
$$B = [0100|0101|0111] = x^{10} + x^6 + x^4 + x^2 + x + 1.$$
The multiplication of $A$ and $B$ over $\text{GF}(2)$ is then
$$C = [0000|0000|...
4
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 coefficients of $Q(x)
= P(x+d)$ are
$$
\hat{Q}(m) = \sum_{i=0}^{n-1} Q(i) \omega^{mi} = \sum_{i=0}^{n-1} P(i+d) \omega^{mi} = \sum_{i=0}^{n-1} P(i) \omega^{m(i-d)} = ...
4
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 value of polynomial modulo 10. We will just say "the remainder of some number" to mean the least positive remainder of that number divided by 10. (The idea and ...
3
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 quadratic equation). so its not really a result on the hardness of a problem per se but rather the impossibility. in this sense it is more analogous to eg a proof of ...
3
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 &= \sum_i y_i+6\sum_{i<j} y_iy_j + 6\sum_{i<j<k} y_iy_jy_k
\end{align*}
$$
And so on. It follows that for $0/1$ inputs, $p_{sym}$ can be written as a ...
3
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 multiplications, not four.
However, there is a more significant point to be made, which is that computing, say, $8x^6$ does not require six multiplications. We have $8x^6 ...
3
You are basically doing an induction definition on $k$, where you evaluate a polynomial in $k+1$ variables by evaluation two polynomials of $k$ variables (by removing $x_1$.) So you have that the complexity $f(k+1)\approx 2f(k)$, which doesn't look polynomial to me.
3
Is this a practical problem or a theoretical problem?
If it a practical problem, it looks to me like standard randomized algorithms for black-box polynomial identity testing should suffice to solve this.
Your polynomial is a multivariate polynomial of degree $n$ over the field $\mathbb{R}$. Pick a set $S$ of real numbers with cardinality $2n$, draw $k$ ...
3
There are FFT algorithms for prime sizes such as Rader's algorithm. Given a factorization of $n$ as a product of (not necessarily different) primes, you can compute the DFT by running Rader's algorithm for each prime, in the same way that the usual FFT works by in effect computing FFTs of size $2$. You can read the details in a paper by Frigo and Johnson ...
3
I am a bit uncertain by what you mean by graphical. One notion is to plot or graph a function, like $y=f(x)$, as you would in a highschool level algebra course. Another notion of "graphical" may include some similar to a Cayley graph. I just want to be upfront that the extent of my knowledge does not extend greatly into topology and some algebraic geometry. ...
3
The conditions $f(1) = p$ and $f(p) = q$ imply the following two equations:
$$
\begin{align}
&\sum_{i=0}^n a_i = p, \\
&\sum_{i=0}^n a_i p^i = q.
\end{align}
$$
When $p < 0$ or $p$ is not an integer, there are no solutions. When $p = 0$, the first equation implies that the polynomial must be $0$ and so $q = 0$.
When $p = 1$, the equations imply ...
3
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 number of zeroes of $f$ is an integer multiple of $2^{n-d}$.
Moreover, for every integer $k \in \{0,\ldots,2^d\}$ there is a degree $d$ Boolean function having ...
3
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^{2^n-1} \equiv 1 \pmod{P(x)}$ (using repeated squaring to do this efficiently), and that for every prime factor $p$ of $2^n-1$, $x^{(2^n-1)/p} \not\equiv 1 \pmod{...
3
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.e., a random permutation in the symmetric group. For example, you can start by randomly picking a pair of variables $x_i,x_j$ and testing whether there exists ...
Only top voted, non community-wiki answers of a minimum length are eligible
