# Questions tagged [polynomials]

The tag has no usage guidance.

95 questions
Filter by
Sorted by
Tagged with
65 views

### Decide whether a polynomial has a root

Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is ...
43 views

### Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n

Here is a question from Computational Complexity by Arora and Barak: Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$. (...
15 views

35 views

### Understanding CRC Computation with PCLMULQDQ

I am currently reading this paper which shows how to calculate CRC using the instruction PCLMULQDQ. I don't quite understand the equations in it yet. Starting with this one for the definition of ...
73 views

### Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?

In the book 'Computational Complexity' by Arora and Barak the following question is posed (exercise 2.20.): Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real ...
47 views

87 views

84 views

### Necessity of convolution operations for product of two polynomials via brute force method

Reference: Page 4 of this document Given two polynomials $p(x)$ and $q(x)$ each of degree $n$ represented in coefficient form, it takes $\mathcal{\Theta}(n)$ time to evaluate given some input $x$. ...
429 views

### Randomized vs deterministic approach for multiset equality

Let $S_1$ and $S_2$ are two multi sets. We want to find, Is $S_1 =S_2$? Algo 1: Sort $S_1$ and $S_2$ and then check $S_1 = S_2$ Running time : $O(n \log {n})$, where $n$ is the size of the multi ...
66 views

### Global Minimum of Multivariate Polynomial is coNP-complete? [closed]

Is the following problem coNP-complete? Inputs: $p=$ a possibly non-convex multivariate polynomial over $\mathbb Z$ $k\in \mathbb Z$, an integer Question: Is $\forall x\in\mathbb Z: p(x)\geq k$?
1k views

### Find a polynomial in two or three queries

Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point. Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$. Output: The $d$ coefficients of polynomial ...
299 views

### How does one generate all the terms of a multivariate polynomial algorithmically?

I was interested in writing a program that given the number of variables and the degree of the multivariate polynomial, it was able to output the multivariate polynomial itself or evaluate it at a ...
42 views

### Update model parameter with new data, discarding old data

I have this dataset, and I am using y = (a * x^n) / (b + x^n) Hill function as the model, where a is the limit of the Hill curve,...
51 views

### Computational complexity of numerically estimating the roots of a polynomial

The Wikipedia article on finding the roots of polynomials mentions all sorts of methods to do so. But it doesn't give, nor can one easily figure out by following the links, known lower and upper ...
97 views

### Approximate a smooth f(x,y) function with a polynomial function

I have a discrete function of two real variables defined as a set of point in a rectangular domain. The function is smooth. I need to approximate it with a polynomial function of the 2nd degree with ...
191 views

### Efficient algorithm to translate/shift polynomials

I have a polynomial $P(x)$, and given some constant $d$, I need to find the polynomial $P(x+d)$. For example, if $P(x)=x^2$ and $d=1$, then the result would be $P(x+1)=(x+1)^2=x^2+2x+1$ (with the ...
109 views

### Lower bound of degree of polynomial approximating parity

Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$ It is known [See e.g. Lemma 5 of this lecture note] that any ...
For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, do we have an efficient way of checking whether there exists an algebra isomorphism between: \frac{\mathbb{F}_q[x]}{\...
How can a polynomial such as $x^3 + 1$ be converted to its binary form of $1001$. Likewise, $10100001 = x^7 + x^5 + 1.$