Skip to main content

Questions tagged [polynomials]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
168 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 ...
Anakin Dey's user avatar
4 votes
0 answers
50 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}...
Quang Dao's user avatar
1 vote
1 answer
65 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 ...
Soham Chatterjee's user avatar
0 votes
0 answers
34 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 ...
Amit Bergman's user avatar
1 vote
0 answers
79 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 ...
Amit Bergman's user avatar
2 votes
0 answers
38 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{...
Mark Schultz-Wu's user avatar
2 votes
1 answer
95 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) \, (...
catalyst's user avatar
3 votes
0 answers
155 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)...
Heda Chen's user avatar
  • 181
0 votes
0 answers
75 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) \...
Rishabh Kothary's user avatar
0 votes
0 answers
90 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 ...
John's user avatar
  • 412
2 votes
1 answer
114 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 ...
Alexey Milovanov's user avatar
3 votes
0 answers
62 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 ...
user6584's user avatar
  • 1,242
4 votes
0 answers
55 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 ...
Thomas Ahle's user avatar
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 ...
Nicola Gigante's user avatar
0 votes
0 answers
66 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,...
Turbo's user avatar
  • 13k
3 votes
0 answers
96 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 ...
AnonTCS's user avatar
  • 71
5 votes
3 answers
249 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). ...
Geoffrey Irving's user avatar
2 votes
1 answer
197 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 ...
Haim's user avatar
  • 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 ...
Rab's user avatar
  • 101
1 vote
0 answers
53 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 ...
TLDR's user avatar
  • 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 ...
luciano's user avatar
  • 61
1 vote
0 answers
58 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 ...
luciano's user avatar
  • 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) =...
user6584's user avatar
  • 1,242
5 votes
0 answers
242 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 $\...
AngryLion's user avatar
  • 173
2 votes
3 answers
139 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 ...
Ken Robbins's user avatar
7 votes
0 answers
247 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 ...
Ari's user avatar
  • 285
2 votes
2 answers
350 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 ...
Ben's user avatar
  • 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 ...
relG's user avatar
  • 209
9 votes
0 answers
169 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 ...
Naysh's user avatar
  • 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$, ...
Sudix's user avatar
  • 151
1 vote
0 answers
113 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 ...
Erfan Khaniki's user avatar
7 votes
2 answers
532 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 ...
Lwins's user avatar
  • 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 $...
Mark S's user avatar
  • 1,125
4 votes
0 answers
251 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 ...
VS.'s user avatar
  • 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}=...
Turbo's user avatar
  • 13k
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 ...
Turbo's user avatar
  • 13k
5 votes
1 answer
205 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 ...
Turbo's user avatar
  • 13k
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 ...
Ludovic Zenohate Lagouardette's user avatar
11 votes
1 answer
580 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 ...
Naysh's user avatar
  • 686
2 votes
0 answers
68 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 ...
Hilder Vitor Lima Pereira's user avatar
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) ...
mghandi's user avatar
  • 360
4 votes
1 answer
387 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 ...
Mark S's user avatar
  • 1,125
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 ...
Turbo's user avatar
  • 13k
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-...
Jacob Edelman's user avatar
2 votes
0 answers
135 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 ...
Alexey Milovanov's user avatar
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 ...
Liam_math's user avatar
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 ...
Mal's user avatar
  • 355
1 vote
0 answers
413 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 ...
Max Hopkins's user avatar
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 ...
Turbo's user avatar
  • 13k
9 votes
0 answers
304 views

What does a private coin $\mathsf{IP}$ protocol for Hilbert's Nullstellensatz look like?

$\mathsf{GNI}$ Private Coin In [GMW85], the authors provided the famous interactive proof $\mathsf{IP}$ of Graph Non Isomorphism $\mathsf{GNI}$. The $\mathsf{GNI}$ protocol entails a verifier ...
Mark S's user avatar
  • 1,125