Questions tagged [polynomials]
The polynomials tag has no summary.
135 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
0
answers
35
views
Is there an efficient algorithm to reduce the degree of a multivariate polynomial given a list of monomial substitutions?
The degree of an $n$-variate polynomial is defined as the maximum degree of the monomials that composes it. Now, given a polynomial $P$ (or rather, a list of monomials, since the coefficients don't ...
1
vote
0
answers
56
views
A Fast Polynomial Multiplication Using only Integers for AKS Algorithm
I'm getting stuck at choosing a fast polynomial multiplication algorithm for the last step of the AKS primality test:
...
5
votes
0
answers
90
views
Is there a sub-quadratic algorithm to evaluate $\Pi_i\Pi_j\Pi_k\Pi_l(1+a_ib_jc_kd_l)$
I'd like to efficiently evaluate $\Pi_i^N\Pi_j^N\Pi_k^N\Pi_l^N(1 + a_ib_jc_kd_l)$ without enumerating the $N^4$ terms by brute force.
I was able to achieve a mildly-efficient $O(N^2log^2(N^2))$ ...
0
votes
0
answers
51
views
Is `f.splitting_field()` a one-way function candidate?
Is computing the splitting field of a polynomial a candidate for a one-way function?
Let $K$ be a number field and $f, g \in K[x]$. Let L_f = f.splitting_field() ...
1
vote
0
answers
36
views
What is the computational complexity of finding the splitting field of a polynomial?
Suppose $K$ is a number field and $f \in K[x]$ is irreducible. What is the computational complexity of computing f.splitting_field()? I'm also interested in the ...
2
votes
1
answer
211
views
NP-hardness of solving systems of *homogeneous* polynomial equations
It is well-known that deciding if a system of quadratic polynomial equations in several variables admits a solution in a finite field is NP-complete. There is a simple reduction from 3SAT, that works ...
0
votes
0
answers
46
views
Multiplying two bivariate polynomials using FFT for univariate polynomials multiplication
Let $$f(x,y)=\sum_{0\le i\le n , 0 \le j \le d}a_{i,j}x^iy^j$$ $$g(x,y)=\sum_{0\le i\le n , 0 \le j \le d}b_{i,j}x^iy^j$$
We want to multiply $f g$.
I did the following: $$f(x,x^{2n+1})=\sum_{0\le i\...
1
vote
1
answer
64
views
Best internal representation of a random variable to enable iterative sampling and interpolation/regression
Let $[0,100]$ denote the interval of real numbers between 0ドル$ and 100ドル$. Given a function $f:[0,100]^n \rightarrow \mathbb{R}^+,ドル I want to implement the following simple algorithm to search for the ...
1
vote
0
answers
138
views
What is the difference between $O$ and $\widetilde{O}$?
We know that $\widetilde{O}(f(n))$ — $O$ with a tilde above it — which means $O(f(n) \text {polylog}(f(n))),ドル i.e., $O(f(n) (\log f(n))^k)$ for some $k$.
Also I have seen in Wikipedia that $n2^n=\...
user avatar
user150715
1
vote
1
answer
79
views
Distinction between square roots in cyclic fields
Let $\mathbb{F}=\mathbb{Z}/p\mathbb{Z}$ a cyclic field. Where $p$ is fixed
Let $(H)_{n\in\mathbb{N}} \in \mathbb{Z}[x_1,\dots]^{\mathbb{N}}$ a family of polynomials with $H_n\in \mathbb{Z}[x_1,\dots,...
0
votes
1
answer
106
views
Sumcheck protocol - how are these 2 polynomials different?
I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf - "Proofs, Arguments, and Zero-Knowledge"
He is describing the Sumcheck Protocol on ...
2
votes
0
answers
180
views
Optimal reassociations is NP-hard?
Consider signed integers with common addition and multiplication.
Reassociation of expression is another equivalent form.
Say expressions:
...
0
votes
1
answer
67
views
Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?
Which function grows faster:
$$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$
Which is true?
$f(n) = O(g(n))$
$g(n) = O(f(n))$
i.e., $f(n) = \Theta(g(n))$
none of the above?
For lower values of ...
0
votes
0
answers
66
views
Progress towards a Polynomial time factoring algorithm?
This is probably insignificant, but I was messing around with polynomials, and found out that, if we have a number, n = pq that we want to factor, if we expand (k+1)^n -k^n - 1, mod n, the first ...
0
votes
2
answers
205
views
Polynomial representations of Boolean functions
The AND boolean function $AND(x)$ can be represented using the polynomial $P(x) = x_1x_2\cdots x_n$. I have a few questions:
Is there a similar polynomial for the PARITY boolean function?
Is there a ...
user avatar
user163048