Questions tagged [polynomials]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6
votes
1answer
5k 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 ...
1
vote
1answer
63 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 ...
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 ...
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 ...
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 ...
6
votes
2answers
441 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 ...
3
votes
1answer
193 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 ...
1
vote
1answer
333 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(...