# Tag Info

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
Accepted

• 270k
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
Accepted

### Converting Polynomials into Binary form

Just put the value of $x=10$ then $$10^3+1=1001$$
• 222

### 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

### 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
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

### 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....
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
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

### 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

### 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 ...
• 143k

### 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

### 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
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
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....
• 143k

### 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
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

### 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