Questions tagged [polynomials]
The polynomials tag has no usage guidance.
2
votes
1answer
37 views
Decidability of factoring algebraic equations
Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution:
$$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$
And some arbitrary factorization constraints, say:...
1
vote
1answer
43 views
How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
2
votes
1answer
52 views
Calculating a polynomial's coefficients from its roots
Let $P$ be a monic polynomial polynomial given by its roots:
$$P(X) = (X-x_1)\times...\times(X-x_n)$$
What is the minimum asymptotic complexity to compute its expansion of the form:
$$a_nX^n+...+a_0$$...
0
votes
0answers
26 views
Polynomial Identity Testing (PIT) and the underlying field
It is well-known that PIT can be done in co-$\mathrm{RP}$ using Schwartz–Zippel lemma. Depending on the underlying field $\mathbb{k}$, $\mathrm{PIT}_\mathbb{k}$ may be in $\mathrm{NP}$ or not. My ...
2
votes
1answer
67 views
Complexity of polynomial interpolation
Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
2
votes
1answer
41 views
No common terms between polynomials: an efficient check?
The "common term" would be in standard form, but the two input multivariate polynomials needn't be, e.g $x(1+y)+y$ and $y(x+a+b)$ have one common term, $xy$.
A brute force solution would be to ...
2
votes
2answers
56 views
How can we prove Schwartz Zippel PIT is applicable to natural polynomials?
The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it?
Perhaps: SZ shows natural polynomials are equal iff it shows those ...
0
votes
0answers
13 views
custom cc 16 bits with Polynomial and Initial Value , algorithm
I generate crc 16 bits with hex Workshop.
Polynomial :1234(hex) Initial Value :5678 (hex) . making it on 010 (ascii) and get 3744.
I looking for this algorithm , I prefer it on c#. but I not find ...
1
vote
1answer
53 views
How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?
I am trying to find the frame check sequence in cyclic redundancy check(CRC). Given that the generator polynomial is $\ g(x)= (x+1)(x^3 + x^2 + 1)$. Let's say the data sequence is $\ 10110001$.
In ...
0
votes
1answer
46 views
How to solve a polynomial of the form y = ax^3 + bx^2 + cx + d using the incremental algorithm in computer graphics
I am studying Computer Graphics and need to design an incremental algorithm for solving the polynomial $y = ax^3 + bx^2 + cx + d$, and then implement that in OpenGL. The input will be the values of $a,...
2
votes
2answers
53 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$.
...
2
votes
1answer
192 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 ...
1
vote
0answers
50 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$?
16
votes
1answer
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 ...
1
vote
1answer
136 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 ...
1
vote
0answers
36 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,...
3
votes
0answers
39 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 ...
3
votes
1answer
60 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 ...
4
votes
1answer
55 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 ...
5
votes
1answer
71 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 ...
1
vote
1answer
58 views
Isomorphism of finite dimensional polynomial algebras over finite fields
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]}{\...
2
votes
3answers
2k views
Converting Polynomials into Binary form
How can a polynomial such as $x^3 + 1$ be converted to its binary form of $1001$. Likewise, $10100001 = x^7 + x^5 + 1.$
-1
votes
1answer
104 views
I would like to know if there is a closed form expression from taking the reciprocal of a polynomial
I would like to know if there is a closed form expression from taking the reciprocal of a polynomial so that I can apply polynomial division to deconvolution using parallel fork-join multithreading.
...
3
votes
0answers
131 views
Algorithm for finding roots of a polynomial modulo prime powers
Given a polynomial $f$ with integer coefficients and a prime power $p^i$, I wish to find a root of $f$ modulo $p^i$, provided one exists, in polynomial or randomized polynomial time in the size of the ...
1
vote
1answer
2k views
Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes
I was reading about CRC coding from two books:
Data Communication and Networking by Forouzan Page 294
Computer Network by Tanenbaum Page 188
They use following notations:
$d(x)$: dataword to be ...
4
votes
2answers
46 views
Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem?
I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\{0, 1, ... n-1\}$, so as to minimize the $L_\infty$ norm, i.e. minimize $\text{max}_{0 ...
0
votes
0answers
36 views
Polynomial Multiplication and Modulo Operation complexity [duplicate]
Given two polynomials of degree $n$ and $m$ over $\Bbb F_q[x]$ it takes about $O((n+m)\log ((n+m)))$ operations ring operations over $\Bbb F_q[x]$ to multiply them.
What is the corresponding bit ...
0
votes
1answer
81 views
CRC error detection
I know that to find an error in signal we have to divide given signal with given polynomial and if 0 remains there is no error. But if I have received signal: 0000 0101 0101 0000 1010 0101 and ...
0
votes
2answers
488 views
Find all rational roots of a polynomial equation
I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range [a, b]. Can someone please tell me which algorithm currently solves the problem with lowest ...
3
votes
1answer
207 views
How to find the symmetry group of a polynomial
Say I have a polynomial in $n$ variables of maximum degree $m$. I define its symmetry group to be the subgroup of the permutation group which fixes the polynomial when it acts on the variables. ...
1
vote
0answers
32 views
Complexity of computing symmetries of a polynomial
Given a polynomial $f\in\mathbb{F}[x_1,\ldots,x_n]$ what is the computational complexity of computing a generating set of the automorphism group of $f$? On first look this seems like a hard problem (...
1
vote
1answer
89 views
Check if a given polynomial is primitve
I try to estimate error detection capabilities of arbitrary CRC polynomials. One important criteria is if a given polynomial is primitive. So I need an algorithm to check that. My goal is to write a C ...
-2
votes
1answer
581 views
Can we evaluate a polynomial of degree N modulo M at all M points, faster than Θ(mn) time?
Given a polynomial $P(x)$ of degree $N$, evaluate $P(x) \bmod M$ at $x = 0$ to $M-1$, where $M$ is a prime number of order $10^6$. Can we do any better than $O(NM)$ given the constraints we only need ...
5
votes
1answer
2k views
Multi-point evaluations of a polynomial mod p
Given a polynomial of degree $n$ modulo a prime number $p$, I want to evaluate that polynomial at multiple values of the variable $x$, what is the best way to do this?
I tried using Berlekamp's ...
0
votes
1answer
121 views
Computing a subproduct tree
Consider the following description of a subproduct tree.
We define a tree T for some points x[0] to x[n-1], and define m = log_2(n).
Tree T is represented as a matrix where each row-column entry i, ...
1
vote
1answer
77 views
Boolean function and real degree
Let $f$ be a boolean function with minimum degree real polynomial representing it be of degree $d$.
Is there a relation between number of zeros $f$ or $1-f$ and degree $d$?
5
votes
0answers
123 views
minimizing computations for evaluating two polynomial simultaneously
I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700.
I ...
2
votes
1answer
47 views
Deterministic query complexity and polynomial degree
What is the current best upper bound known on deterministic decision tree complexity of a Boolean function in terms of its polynomial degree? Also, what is the current widest separation known between ...
1
vote
1answer
196 views
Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials
I want to find the minimal period of any state of an LFSR (except the initial state of all zeroes) whose characteristic polynomial is the product of two primitive polynomials.
In particular, $f(x),g(...
2
votes
1answer
143 views
How to revert a carryless polynomial multiplication?
In the carryless multiplication of two polynomials in a 8-bit environment, is it possible to obtain the original 8-bit values from the result?
As an example:
$$\begin{align}
(x^{11} + x^{10} + x^9 ) ...
5
votes
1answer
954 views
BSS-model Computational complexity of finding the roots of a polyomial
I'm currently dealing with a problem for which I could show that an exact algorithm would imply a general algorithm for finding the real (but not complex) roots of an arbitrary univariate polynomial ...
1
vote
1answer
641 views
What is the use of Horner's Method?
Here is Wikipedia's explanation of Horner's Method:
Given the polynomial
$$
p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,
$$
where $a_0, \ldots, a_n$ ...
6
votes
4answers
2k views
Calculating the number of multiplications necessary to evaluate a polynomial
I was watching a lecture and got confused over a slide. This is what it says:
Consider a polynomial - first representation
$$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$
The ...
9
votes
1answer
932 views
Algorithm for multiplying multivariate polynomials
Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$.
How fast can we compute the product of $f$ ...
16
votes
3answers
510 views
Is there a complexity viewpoint of Galois' theorem?
Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...
1
vote
0answers
45 views
How to find (real-valued) roots of matrix polynomial
Assume you have a fixed ($d=O(1)$ for that matter) degree matrix polynomial
$$P(X)=A_0+A_1\cdot X+A_2\cdot X^2+\ldots+A_dX^d$$
Where $A_0,A_1,\ldots A_d\in\mathbb N^{n\times n}$ are given as input. ...
1
vote
1answer
164 views
Lower bound on approximation degree in Nisan-Szegedy
In Nisan and Szegedy's 1994 paper "On the degree of boolean functions as real polynomials"[1] Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\,\tfrac16\mathrm{bs}(f)\,}$? It ...
1
vote
1answer
54 views
Relations among different boolean approximations
Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$).
Let $p$ be the minimum degree (of degree $d_f$) real polynomial ...
6
votes
1answer
63 views
Fast polynomial calculation over $\mathbb{Z}_{487}$
Given a polynomial $a(x)$ of degree at most $242$ over $\mathbb{Z}_{487}$, I'd like to choose distinct values $x_0, x_1, . . . , x_{242} ∈ \mathbb{Z}_{487}$, such that I'll be able to calculate $a(x_j ...
1
vote
0answers
93 views
Connection between formula size and time complexity
Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree.
Is there a connection between ...
