Questions tagged [polynomials]
The polynomials tag has no usage guidance.
118
questions
2
votes
0
answers
82
views
Multipoint evaluation in Lagrange basis
Setup. Let $\mathbb{F}$ be a finite field with a multiplicative subgroup $E = \{e_1, \dots, e_k\}$ of order $k$. Given a list $y = y_1, \dots, y_k\in \mathbb{F}$ let $p$ be the unique polynomial of ...
3
votes
1
answer
182
views
Polynomial Identity Testing for $\prod \sum \prod$
I am reading a survey on polynomial identity testing by Saxena. On page 6 he writes that PIT for depth-3 circuits of the form $\prod \sum \prod$ is trivial. He gives no citation and as such I believe ...
- 33
4
votes
0
answers
52
views
Complexity of solving random underdetermined polynomial equations over finite fields
Consider a random system of degree-$d$ polynomials, with $n$ variables and $m$ equations, over some finite field $\mathbb{F}_q:$
$$\begin{align}\sum_{\substack{(\alpha_1,\dots,\alpha_n) \in \mathbb{Z}...
- 41
1
vote
1
answer
69
views
Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$
Given any matrix of univariate polynomials of degree $\leq n^{O(1)}$ then prove that the coefficent of $x^i$ in the determinant of the matrix is in $GapL$
Hint: Use Mahajan-Vinay's result of ...
- 280
0
votes
0
answers
36
views
Hardness of finding minimal subsets that will change the maximum of a univariate polynomial
Given a univariate polynomial of the form $p(x) = \prod_{0 \leq i \leq N}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$ (we are given all ...
- 11
1
vote
0
answers
82
views
Hardness of maximization of a univariate polynomial (as a function of its degree)
Given a univariate polynomial of the form $p(x) = \prod_{i}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$.
What is the complexity of ...
- 11
2
votes
0
answers
40
views
Generalization of Binary Decomposition to Polynomials?
Given an integer $x\in\mathbb{Z}$, we can write its binary decomposition (and more generally base $B$ for $B\in\mathbb{Z}$, $B>1$) as
$$x = \sum_{i=0} x_i B^i,$$
where $x_i \in \mathbb{Z}/B\mathbb{...
- 978
2
votes
1
answer
100
views
Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing
$\newcommand{\bigparen}[1]{\Bigl ( #1 \Bigr )}$
I'm working with polynomial hashes $H$ defined by the pair $(B, M)$ (base, modulo):
$$H_{B, M}(s) \equiv \sum_{i=0}^{n-1} B^{n-1-i} \cdot conv(s_i) \, (...
- 23
3
votes
0
answers
156
views
The $O(n^{1/r})$ upper bound of polynomial degree of OR over composite moduli
$\newcommand{\OR}{{\sf OR}}
\newcommand{\MOD}{{\sf MOD}}
$In the paper Representing Boolean functions as polynomials modulo composite numbers, Barrington, Beigel and Rudich showed that $\delta_m(\OR_n)...
- 181
0
votes
0
answers
81
views
Can every reducible multivariate polynomial be partitioned into product of univariate polynomials of algebraically independent elements?
Lets say we define a reducible multivariate $f \in \mathbb{F}[x_1,...,x_n]$ to be partionable by $y_1,...,y_r \in \mathbb{F}[x_1,...,x_n]$ iff
\begin{equation}
f(x_1,,,,.x_n) = f_1(y_1)\cdot f_2(y_2) \...
- 143
0
votes
0
answers
93
views
When Exponential Costs are Essential for NP-Hardness?
In many NP-hard problem there is a budget constraint. Each element $e$ in the instance has a certain cost $c(e)$ and a profit $p(e)$; a feasible solution $S$ for the considered problem cannot exceed ...
- 412
2
votes
1
answer
122
views
Complexity of computation of ANF-form (Zhegalkin polynomial)
Let $f: \mathbb{F}_2^n \to \mathbb{F}_2$ be a boolean function.
Consider $f$ as a multilinear polynomial over $\mathbb{F}_2$ (algebraic normal form or Zhegalkin polynomial).
How hard is to define the ...
- 2,013
3
votes
0
answers
66
views
Efficiently checking that points lie on a polynomial
Say I am given $n$ points $y_1, …, y_n$ in a finite field, and want to check whether they lie on a polynomial $f$ of degree $t < n-1$ with $f(i)=y_i$. The obvious way to do this is to interpolate a ...
- 1,242
4
votes
0
answers
62
views
Error analysis of Estrin's method
Estrin's Method is an alternative to Horner's method for evaluating polynomials. To evaluate a polynomial $P(x)=\sum_{i=0}^7 a_i x^i$ at a point $x\in\mathbb R$, it first computes the powers $x^2$ and ...
- 958
14
votes
2
answers
2k
views
Algebraic equivalent of SAT?
Starting with a simple observation. If $x,y\in\{0,1\}$, then the arithmetic product $x\cdot y$ corresponds to the logical conjunction if we interpret $1$ as true and $0$ as false.
But then, for a ...
- 1,704
0
votes
0
answers
67
views
Polynomial GCD exact complexity in terms of degree and number of variables
https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $\mathbb F_p[x_1,x_2,\dots,...
- 13.1k
3
votes
0
answers
97
views
Sparsity Bounds for Probabilistic Polynomials
Has there been any research done on proving sparsity lower bounds for probabilistic polynomials (over the Reals) for Majority?
A probabilistic polynomial is a distribution of polynomials $D$ such that ...
- 71
5
votes
3
answers
255
views
Extracting coefficients of polynomials given by straight line programs
Consider a straight line program of length $L$ that takes one input $x \in \mathbb{R}$ and computes a polynomial $p(x)$, using only addition, multiplication (including multiplication by constants). ...
- 3,263
2
votes
1
answer
198
views
Complexity of finding approximate solutions for systems of polynomial equations
Consider the following problem:
Input: $(p_1,...,p_n, \epsilon)$ where each $p_i$ is a polynomial in $m$ variables with integer coefficients and $\epsilon>0$.
Output: If there is $(r_1,...,r_m) \in ...
- 23
-1
votes
1
answer
67
views
Interpolation to find polynomial multivariate derivative
This question came when reading a paper here about affine projections of polynomials.
The publisher claims in Proposition 22 that
Let $f(\mathbf{x}) \in F[\mathbf{x}]$ be an $n$-variate polynomial of ...
- 101
1
vote
0
answers
54
views
Evaluating multidimensional polynomials
Are there efficient algorithms to construct optimal evaluators of multivariable polynomials? Here, an 'evaluator' can be thought of as an algorithm or description of how to evaluate a specific ...
- 119
1
vote
0
answers
57
views
Partition of multisets of polynomials
Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product ...
- 61
1
vote
0
answers
59
views
Computational complexity of factoring univariate polynomials with positive integer coefficients
I am interested in the computational complexity of the following problem.
Input: a polynomial p(x) with positive integer coefficients
Output: a factorization of p(x) into irreducible factors having ...
- 61
1
vote
0
answers
77
views
BCH codes and polynomials with many values in a subfield
For points $P=\{x_1, \ldots, x_n\} \subset {\mathbb F}_{2^m}$ define $$\mathcal{C}(P, t) =\{(f(x_1), \ldots, f(x_n)) \mid \mbox{$f\in {\mathbb F}_{2^m}[X]$ has degree $t$}\}$$ and $\mathcal{C}'(P, t) =...
- 1,242
5
votes
0
answers
243
views
$\#$P hardness of computing weighted sum of degree $2$ polynomials
Consider polynomials $f: \{0, 1\}^{n} \rightarrow \{0, 1\}$ over $\mathbb{F}_2$ (addition and multiplication are taken modulo $2$.) Consider integers $x \in \{0,1\}^{n}$, written in binary. Let $\...
- 193
2
votes
3
answers
141
views
Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy
Let there be a set of $P$ polynomial equations $f_j(x_1,x_2...x_V)=0$ where $1\leq j\leq P$. For each $f_j$ the coefficients are real and every variable goes up to degree $D$. It is also guaranteed ...
- 123
7
votes
0
answers
250
views
How is a "low-degree polynomial" precisely defined in Algebrization?
I'm going through papers which present algebrization as a barrier and I'm trying to understand how "low-degree" polynomials are precisely defined, i.e. are they low with respect to the ...
- 285
2
votes
2
answers
360
views
What is the polynomial representation of the Hamming weight function?
For any function $f: \{1,-1\}^n \rightarrow \{1,-1\}$, there is a unique multilinear polynomial $p \in \mathbb{R}[x_1,\dots, x_n]$ for which $p(x)=f(x)$ for all $x \in \{1,-1\}^n$ (see e.g. Lemma 4.1 ...
- 123
4
votes
0
answers
112
views
efficiently computing a sum of products of polynomials
Let $F$ be a prime finite field. Let $d$ be a power of two dividing $p-1$. Suppose I have $d$ pairs of univariate polynomials $f_i,g_i$ over $F$ for $i=1,\ldots,d$. All have degree less than $d$.
I ...
- 209
9
votes
0
answers
170
views
What are some examples of algorithmic applications of noncommutative rational identity testing?
The problem of polynomial identity testing (PIT) is known to be in $\mathsf{RP}$, but not known to be in $\mathsf{P}$.
The related problem of noncommutative rational identity testing (NCIT) is known ...
- 686
5
votes
0
answers
171
views
Complexity of extracting a coefficient of a polynomial in multiple variables
I'm looking for efficient algorithms for problems of the following type:
Let's say we have the variables $x_1,...,x_n$.
Over these variables, we are given a function $p_1\cdot ... \cdot p_m$, ...
- 151
1
vote
0
answers
114
views
Switching lemma for polynomials over $\mathbb{F}_2$
Suppose $f$ is in $\mathbb{F}_2[x_1,...,x_n]$ with total degree $d$.
Q. Is there any kind of switching lemma or restriction lemma in which by applying the lemma on $f$ we can reduce the total ...
- 342
7
votes
2
answers
544
views
Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power
It seems to be a folklore that we can "handle" $\textrm{ACC}[q]$ circuits not only for prime $q$ but prime power $q$.
For example, authors of this paper say that
... any constant
depth circuit ...
- 395
1
vote
0
answers
185
views
Can a hash preimage be used to amplify BPP probabilities?
Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$. A standard way to do this is to use a classical PRG to randomly sample a number $...
- 1,145
4
votes
0
answers
252
views
Testing emptiness property complexity in Sum of Squares Proof systems
Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where $$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb ...
- 539
1
vote
0
answers
103
views
Complexity of planted root of a system of quadratic homogeneous polynomials?
Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\dots=f_{m}=...
- 13.1k
1
vote
0
answers
26
views
Worst case polynomial in elimination theory under rank conditions?
Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree ...
- 13.1k
5
votes
1
answer
209
views
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total ...
- 13.1k
2
votes
0
answers
1k
views
Complexity of solving a polynomial equation
Given a polynomial equation of degree n with m variables, that is guaranteed to have at least one solution, what is would be the ...
11
votes
1
answer
594
views
How "hard" is it to maximize a polynomial function subject to linear constraints?
General Problem
Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
- 686
2
votes
0
answers
69
views
Bit complexity of factoring univariate polynomial over $\mathbb{Q}$ (rationals)
What is the bit complexity of finding all the irreducible factors $f_1, ..., f_r$ of a degree-$d$ polynomial $f(x) = \sum_{i=0}^d a_i\cdot x^i \in \mathbb{Q}[x]$ whose all coefficients are $B$-bit ...
6
votes
2
answers
1k
views
a polynomial representation of boolean functions
I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) ...
- 360
4
votes
1
answer
388
views
If a root||nonce Proof-of-Work certificate is prime, can it be used in any other interesting proofs?
Because Bitcoin and many other cryptocurrency mining certificates are "rare" in that their respective hash is less than a very small number, can we leverage their rarity in probabilistic proofs of ...
- 1,145
2
votes
0
answers
66
views
Does deterministic PIT produce deterministic irreducible polynomial generation?
In $\Bbb F_q[x]$ given $d\in\Bbb N$ there is a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=deg(x)$ under $GRH$ and an unconditional randomized algorithm.
Do ...
- 13.1k
11
votes
1
answer
377
views
Is there a P-complete problem on diophantine equations?
In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem. I believe that deciding if a quadratic diophantine equation has any solution is NP-...
- 111
2
votes
0
answers
136
views
On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits
As I understand from the survey "Progress on Polynomial Identity Testing - II"
a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown.
However, there exists paper ...
- 2,013
1
vote
0
answers
100
views
Deciding reachability under iterated independent polynomial mapping
For any $1\leq i\leq m$, $f_i: \mathbb{Q}\rightarrow \mathbb{Q}$ is a polynomial mapping over $x_i$, where $\mathbb{Q}$ is the set of rationals. For $\vec{a}_0=(a_1, \cdots, a_m)\in \mathbb{Q}^m$, we ...
- 21
2
votes
0
answers
227
views
Proof of a (simple) lemma by Aaronson
I am reading this article, and I need help with an apparently obvious proof.
The lemma (on page 5), that I want to know the proof of, is this: Let $p : \{0,1\}^N \rightarrow \mathbb{R}$ be a real ...
- 355
1
vote
0
answers
415
views
Computational complexity of polynomial interpolation with k non-zero terms
I am attempting to find a complexity for computing the order polynomial of partially ordered sets on a special family, and have come across the following problem. Assume we have the following values ...
- 225
3
votes
0
answers
47
views
Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?
Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ is irreducible what is the best technique to factor such ...
- 13.1k