Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

4
votes
1answer
99 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 ...
2
votes
0answers
89 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 ...
6
votes
1answer
135 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 ...
2
votes
0answers
47 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
2answers
499 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) ...
4
votes
1answer
251 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
vote
0answers
54 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 ...
0
votes
0answers
40 views

Digraph game reduction problem

Let A and B be 2 players and D=(V,E) a digraph and v0 an fixed vertex. A chose v0 v1 B chose v1 v2 and so on.The player who can't chose anymore loses.(they are not allowed to chose an edge adjacent ...
12
votes
1answer
273 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-...
2
votes
0answers
79 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 ...
1
vote
0answers
90 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 ...
2
votes
0answers
180 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 ...
1
vote
0answers
180 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 ...
3
votes
0answers
44 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 ...
10
votes
0answers
267 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 ...
9
votes
0answers
167 views

Fast algorithm for composing Boolean polynomials

Question: Is there a practically fast algorithm to compose Boolean polynomials ($\mathbb{F}_2[x]$) modulo a fixed Boolean polynomial? Background: I would like random access within Vigna's xorshift128+...
3
votes
2answers
161 views

Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

Since every $3$-SAT instance with $n$ variables can be expressed as a degree-$3$ polynomial over $\mathbb{F}_2$ with $n$ unknowns, the NP-hardness of $3$-SAT directly translates to NP-hardness of ...
5
votes
0answers
186 views

Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?

Given a primitive polynomial (gcd of coefficients is $1$) in $\Bbb Z[x]$ we have a polynomial time factoring algorithm for this that runs in time polynomial in degree $d$ and number of bits in ...
6
votes
1answer
187 views

Finding a positive point for a collection of polynomials

I am wondering about the complexity of the following problem: Given $k$ polynomials $p_1(x_1, \ldots, x_n)$, $p_2(x_1, \ldots, x_n)$, $\ldots$, $p_k(x_1, \ldots, x_n)$ over the $n$ real ...
10
votes
2answers
143 views

Maintaining the value of a polynomial over a dynamically updated input

Let $P(x_1, x_2, \ldots, x_n)$ be a polynomial over a fixed finite field. Suppose we are given the value of $P$ on some vector $y \in \{0,1\}^n$ and the vector $y$. We now want to compute the value ...
3
votes
0answers
73 views

Finding degree two subfield

Let $K=\frac{\mathbb{Q}[x]}{<f(x)>}$ where $f(x)$ is irreducible over $\mathbb{Q}$ and has even degree. I want to find $K_2$ such that $ \mathbb{Q} \subseteq K_2\subseteq K$ and $[K_2:\mathbb{Q}]...
1
vote
0answers
70 views

Optimal evaluation of polynomials / rational functions

A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the ...
6
votes
0answers
108 views

Algebraic dependence of roots of irreducibles over a finite field

I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math....
1
vote
0answers
73 views

Approximating circuits with polynomial of low degree, can't understand small detail in the proof

I'm looking at the proof of this lemma: Lemma For every integer $t>0$, there exists a (proper) polynomial of total degree $(2t)^d$ that differs with $C$ on at most $size(C) 2^{n-t}$ inputs Where ...
0
votes
0answers
58 views

Identity testing of margins of boolean functions

Consider a boolean function $f(\vec{x},\vec{y})$, we define an (integer-valued) function $g(\vec{x})=\sum_{\vec{y}}f(\vec{x},\vec{y})$, i.e., $g$ can be considered as a (sort of) margin of $f$. The ...
1
vote
1answer
197 views

Existence of solution for a system of multi-variate polynomial equations and in-equations

Formally, I have 2 finite sets of polynomials : $P = \{p_1, p_2, p_3, ...p_m\}$ and $Q = \{q_1, q_2, q_3, ...q_n\}$, where for $1 \leq i \leq m$, and $1 \leq j \leq n$, I have $p_i, q_j \in \mathbb{C}...
5
votes
1answer
136 views

A special case of the boolean multivariate quadratic polynomial problem

It's well known that in the general case, the boolean MQ problem: given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = 0$...
7
votes
2answers
246 views

How to find a non-zero point of a non-zero polynomial of low degree?

Given a circuit that computes a polynomial $P(x_1 \dots x_n)$ of low formal degree over some large field $\mathbb{F}$. Moreover, given a point $X \in \mathbb{F}^n$, such that $P(X) \neq 0$. Can one ...
10
votes
1answer
218 views

Evaluating symmetric polynomials

Let $f:\mathbb{K}^n \to \mathbb{K}$ be a symmetric polynomial, i.e., a polynomial such that $f(x)=f(\sigma(x))$ for all $x \in \mathbb{K}^n$ and all permutations $\sigma \in S_n$. For convenience, we ...
5
votes
1answer
275 views

Complexity of multi-linear polynomial computing Boolean function

Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual, let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest Boolean circuit computing $f$. As we know that every ...
1
vote
0answers
55 views

The curve used in Parvaresh-Vardy decoding

Consider the Parvaresh-Vardy list decoder. As I understand it, the idea is to decide on a curve over an extension field of the form $(f,f^h mod E, f^{h^2} mod E,\dots)$ and then evaluate each of ...
0
votes
0answers
60 views

Complexity of variant polynomial factorization

Few years back a question on whether a variant of integer factorization was $\mathsf{NP}$ complete was asked, which according to state of mathematics today does not have a conclusive answer. Is ...
1
vote
0answers
150 views

Algorithm for multiplying multivariate polynomials in a commutative ring

Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multivariate polynomials with the same $x_i$-terms with maximal total degree $\delta$, but with different ...
1
vote
1answer
171 views

Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?

Let $\underline{x}\triangleq x_1,\dots,x_n$. Given a Boolean function $f:\{0,1\}^n\to\{0,1\}$, we say that $p(\underline{x})\in\Bbb{R}[\underline{x}]$ is an $\epsilon$-approximation to $f$ if for ...
1
vote
2answers
259 views

Does approximation degree of AND depend on error?

Denote $\underline{x}\triangleq x_1,\dots,x_n$. Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $p_\epsilon(\underline{x})\in\Bbb R[\underline{x}]$ be minimum multilinear multivariate ...
7
votes
1answer
207 views

What do we know about checking real-stability of multivariate complex polynomials?

Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root ...
1
vote
0answers
68 views

complexity of factoring multivariate polynomials over Fn

recently multivariate polynomial factoring has been related to Polynomial Identity Testing / PIT (by Kopparty, Saraf, Shpilka). where is the complexity of factoring multivariate polynomials over ...
10
votes
1answer
255 views

On derandomizing polynomial identity testing

In polynomial identity testing we seek a deterministic algorithm to infer equality of two polynomials $g,h\in\Bbb Z[x_1,\dots,x_n]$. Derandomizing known efficient randomized algorithms and producing ...
2
votes
0answers
112 views

Universal constant for bivariate testing

In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate ...
5
votes
0answers
111 views

Optimizing over symmetric polynomials [closed]

Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that (i) $0 \...
0
votes
1answer
160 views

Idea for a white-box PIT deterministic algorithm in polynomial time

Just a warning, I am an amateur and this algorithm probably doesn't work. A high level description of the algorithm: Be $f(x_1,...,x_n)$ a polynomial, $n$ the number of variables and $d$ is the ...
4
votes
2answers
305 views

Is there a polynomial time algorithm for creating a set of vectors in general position?

It seems to be possible to create a set of vectors in $\mathbb{R}^n$ such that any subset of $n$ vectors forms a basis. For example, in $\mathbb{R}^3$, here is such a set with 21 vectors: $$ \left\{ ...
4
votes
0answers
86 views

Low-degree testing in PCP Theorem using bivariate polynomials

I read about modifications of the low-degree test used in the (first) proof of the PCP theorem. The test used in the proof works over randomly chosen lines while modifications allow choosing random ...
9
votes
1answer
180 views

Randomized identity-testing for high degree polynomials?

Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime. Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with time ...
3
votes
1answer
160 views

Efficient Shamir secret sharing reconstruction

Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the ...
2
votes
1answer
165 views

An upper bound over the number of bipolar orientations for a regular graph

Given a $k$-regular graph $G$, the number of acyclic orientations $Acy(G)$ is $\chi(-1)$ where $\chi$ is the chromatic polynomial of $G$. How many bipolar orientations does $G$ have? Is there an ...
3
votes
2answers
170 views

Root finding in [0,1]

I am interested in the problem of finding a real root of a polynomial equation $f(x)=0$ where $f(x)=\sum_{i=0}^n a_ix^i$. Is it possible to give a reduction, i.e, to compute a different polynomial $g$ ...
4
votes
0answers
100 views

The rank-polynomial of a graded poset

Let $P$ be a graded poset with rank function $r$. We may then define its rank-polynomial as: $R_P(q) = \sum_{x \in P} q^{r(x)}$. This definition can be applied to several interesting posets, for ...
6
votes
1answer
137 views

Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?

If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether ...
23
votes
3answers
1k views

Representing OR with polynomials

I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such: $p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\...