Questions tagged [polynomials]
The polynomials tag has no usage guidance.
92
questions
0
votes
1answer
20 views
Represent a DNF formula as a multivariate linear formula?
Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$
How do I convert that into a polynomial form?
1
vote
0answers
32 views
How do I decode a received polynomial code with an error?
As a message I get (5,0,1,3), which is coding a sequence of numbers of length 2 in $\mathbb{F}_7$ as polynom with the 4 support points a1 = 0, a2 = 1, a3 = 2, a4 = 6. In the transimission occured an ...
1
vote
1answer
136 views
Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$
Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$.
For eg. Let the array be $1,2,3$ then my answer will be calculated as-
$(2-1)$.$(...
2
votes
0answers
34 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 ...
2
votes
1answer
70 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 ...
1
vote
0answers
47 views
How to compute the first n coefficients using number theoretic transform (NTT)?
I need to find the first $n$ coefficients of $$\prod_{i = 1}^{i = q}(1 + x^{a_i})^{b_i}$$ modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity $O(n\log n)$ or $O(...
2
votes
1answer
79 views
Why does $x^{15}+x^{14}+1$ detect all errors at most 32768 bits apart?
Reference Question from Forouzon Book Computer Network.
Find the status of the following generator related to two isolated, single-bit errors.
$$x^{15} + x^{14} + 1$$
Answer given :
This polynomial ...
0
votes
0answers
24 views
What is the meaning of “a polynomial amount/number of operations” in these contexts? [duplicate]
I am currently reading the book ''The Outer Limits of Reason'' and encountered a description about which I am very confused. I am afraid to say, this may be due to the fact that I am not a native ...
3
votes
0answers
23 views
Bit complexity of computing the sign of an expression evaluated at an algebraic number
I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
3
votes
1answer
146 views
Is O(n log n) exponential speedup over O(n^2)?
I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?
0
votes
0answers
101 views
Multiplying bivariate polynomials using FFT
Consider two bivariate polynomials of degree at most $n-1$ in each variable:
$$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^i y^j \quad \text{and} \quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^i y^j. $$
...
12
votes
2answers
2k views
What is the most efficient algorithm to compute polynomial coefficients from its roots?
Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is $y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$. To get the coefficients (i.e. $y = \sum_{i}^n a_i x^i$), a ...
2
votes
1answer
54 views
Polynomial multiplications and counting
I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically ...
1
vote
1answer
60 views
Fitting a polynomial to a set of points or to a skeleton
Available data
Available to me is a set of points which can be represented as shown in image 1:
Also available to me is a non-continuous path derived from this data. It is not important how this non-...
1
vote
0answers
25 views
Generating a set of divergence-free basis
I'm trying to derive an algorithm that would generate a set of divergence-free vectors, which shall be used as basis vectors later on. Using a simple example, a 2D second-order divergence-free basis ...
2
votes
1answer
72 views
Polynomials - using Newton's method, or not?
I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed.
I can use general Newton's ...
3
votes
1answer
65 views
Polynomial size Boolean circuit for counting number of bits
Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
2
votes
1answer
29 views
Question on the paper ``Self-Testing/Correcting for Polynomials and for Approximate Functions''
I am having some trouble really getting to a precise understanding of some of Self-Testing/Correcting for Polynomials and for Approximate Functions and would greatly appreciate help. Here is my ...
2
votes
2answers
47 views
Search for numerical solutions of underdetermined systems of quadratic equations
I'm looking for an algorithm that can quickly generate an approximate real number solutions of an underdetermined quadratic system. My task is to explore its algebraic variety. I'm interested in a ...
1
vote
1answer
224 views
CRC computation speed vs polynomials features
I tried to find information about how features of a CRC polynomials influence computation speed of implementations.
It is obvious that (depending from the CPU architecture the algorithm runs on) ...
3
votes
1answer
866 views
Meaning of polynomially larger or smaller in the context of the master method
I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
3
votes
1answer
99 views
Last digit of polynomial value
There is a simple-looking problem.
Given integer coefficients $c_{0}, c_{1}, c_{2}, \dots, c_{n - 1}$ of polynomial $$ p(x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots + c_{n - 1} x^{n - 1} $$ and ...
0
votes
1answer
448 views
Polynomial multiplication coefficients
I was wondering about the following interesting questions:
Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial.
What about finding a specific ...
2
votes
1answer
113 views
Polylogarithm growth rate proof using Polynomial growth equation
In the CLRS, there's this part, where it's shown that $$\lim_{n\to\infty}\frac{(n^b)}{(a^n)} = 0$$ In the same chapter, it uses the aforementioned equation to prove that any polylogarithm function ...
2
votes
0answers
50 views
An efficient algorithm to find a linear transformation between two ternary quadratic forms
Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms
$$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\
Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$
over the field $\mathbb{F}...
3
votes
1answer
86 views
Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?
I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following:
Let $F(x)$ be given as a product
$F(x) = \prod_{...
4
votes
1answer
80 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
47 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
565 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$$...
2
votes
1answer
279 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
43 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
74 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
18 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 it....
1
vote
1answer
130 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
269 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
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$.
...
2
votes
1answer
427 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
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$?
17
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 ...
2
votes
1answer
296 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
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,...
3
votes
0answers
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 ...
3
votes
1answer
96 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 ...
5
votes
1answer
186 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
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 ...
1
vote
1answer
60 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]}{\...
5
votes
4answers
8k 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
111 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.
...
2
votes
0answers
197 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 ...
2
votes
1answer
4k 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 ...
