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

• 278k

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

### Converting Polynomials into Binary form

Just put the value of $x=10$ then $$10^3+1=1001$$
• 232
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 ...
• 278k
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})$). ...
• 409
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, ...
• 22.3k

### 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 ...
• 8,303

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

### 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.
• 11.6k
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 ...
• 7,088
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 ...
• 162k
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(...
• 30.7k
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 ...
• 30.7k

• 9,837
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 ...
• 278k

### 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,898
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$. ...
• 39.1k
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 ...
• 39.1k