Questions tagged [polynomials]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-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
198 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 ...
4
votes
2answers
62 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
54 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
109 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 ...
1
vote
2answers
849 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
388 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 (...
2
votes
1answer
137 views

Check if a given polynomial is primitive

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 ...
-1
votes
1answer
670 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 ...
6
votes
1answer
4k 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
194 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
112 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
128 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
90 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
293 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
180 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
1k 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
1k 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
3k 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 space complexity is 100 ...
9
votes
1answer
1k 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
689 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
52 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
205 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
57 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
73 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
104 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 ...
1
vote
0answers
41 views

Degrees of polynomials representing Boolean functions

Let $$B_1=\vee_{i_1=1}^d\wedge_{i_2=1}^d\dots\vee_{i_{2r-1}=1}^d\wedge_{i_{2r}=1}^dX_{i_1i_2\dots i_{2r-1}i_{2r}}$$ $$B_2=\wedge_{i_1=1}^d\vee_{i_2=1}^d\dots\wedge_{i_{2r-1}=1}^d\vee_{i_{2r}=1}^dX_{...
1
vote
1answer
173 views

Proof of Minsky Papert Symmetrization technique

I frequently hear about the Minsky-Papert Symmetrization technique in many papers with a reference to the book of Minsky. I could not locate the book online. Could someone supply me a proof of the ...
2
votes
1answer
69 views

Multiplication of two or more algebraic quantities [closed]

Recently, I was facing the problem how to multiply to two or more algebraic quantities in c++. For example, if the two algebraic quantities are $$x^2-2x+3, \text{and } x-5$$ then the result of ...
1
vote
1answer
35 views

Comparing coefficients of boolean functions

Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the ...
0
votes
1answer
77 views

efficient algorithms for factoring polynomials [closed]

Does anyone know what are the most efficient algorithms for factoring polynomials in a field of characteristic zero, i.e, a field that may contain infinitely many elements. I'm mainly concerned within ...
4
votes
1answer
198 views

How to find degree of polynomial represented as a circuit?

I know very little about arithmetic circuits, so maybe it is something well-known. Given a small circuit consisted of $\{1,x,-,+,*\}$ defining one variable polynomial. Let be additionally known that ...
2
votes
0answers
57 views

Polynomials and NSA [closed]

I'm looking for some applications of criteria of irreducibility of integer polynomials inside and outside mathematics. I was reading the of CV Filaseta, a great researcher in this area and he has ...
2
votes
1answer
428 views

Do you know of a brute-force algorithm for optimizing polynomial expressions? [closed]

For instance, given the polynomial expression $xy + x + y + 1$ it will output $(x+1)(y+1)$. Thanks!
1
vote
1answer
75 views

Complexity of general polynomial map evaluation is polynomial?

A polynomial map is equal to another polynomial map iff they take on the same values at each point. So this is different from formal polynomials. So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x \...
7
votes
2answers
370 views

Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of ...
7
votes
3answers
7k views

Finding constants C and k for big-O of fraction of polynomials

I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for finding the ...
6
votes
2answers
410 views

Testing whether a determinant polynomial is identically zero

Suppose we are given matrices $A_1, \ldots, A_k$ which are $n \times n$ matrices with rational entries and are asked to determine whether the polynomial ${\rm det}(\alpha_1 A_1 + \alpha_2 A_2 + \cdots ...
4
votes
1answer
186 views

Discrete fourier transform of a polynomial whose degree is not a power of 2

I need to evaluate a polynomial of degree n at the n cube roots of unity. Simple evaluation would take $O(n^2)$ time. I know that polynomial evaluation can be done in $O(n\log n)$ time using FFT. But ...
0
votes
1answer
100 views

Snowball Question FFT

http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdf I'm confused as to the solution for the snowball question. To start with, I have two specific questions: (1) Each pair $a_i,...
2
votes
3answers
163 views

Writing a program to find polynomial $f(x)$ from $f(1)$ and $f(f(1))$

Let $f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n$, where $a_i\ge0$ and $a_i$ is integer. Given $f(1)=p$ and $f(f(1))=q$, we have to find $a_0$, $a_1$, $a_2$, $a_3$, $\dots$, $a_n$, where such $f(x)$ exists. Or ...
3
votes
2answers
163 views

What does it mean to multiply or divide polynomials?

What does it mean to multiply or divide polynomials? I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical ...
5
votes
1answer
93 views

Rearrange a sequence of real numbers to satisfy polynomial inequalities

Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$). Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$...

1
2