# Questions tagged [polynomials]

The tag has no usage guidance.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
363 views

### Looking for an operator on polynomials

I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc). I wonder ...
296 views

### Exponential-time factorization of polynomials

Let an explicit field be a field for which equality is decidable (in some standard model of computation). I am interested in the factorization of univariate polynomials over an explicit field. It is ...
323 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-...
136 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 ...
290 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 ...
179 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+...
189 views

### Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)

I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ ...
139 views

### Computing the Fourier-Walsh coefficients of an arithmetic circuit

Given an $f$-fan in arithmetic circuit of depth $d$ over $GF(q)$ (for some prime $q$) and the set of variables $(x_1,\ldots,x_n)$, what is the state of the art upper bound for calculating the Fourier-...
166 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$, ...
109 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....
204 views

### Is there an interpretation of the degree of the polynomial computed by the arithmetization of a boolean formula?

If I understand this correctly, arithmetizating a formula is a way of "interpolating" a polynomial in such a way that polynomial evaluated on 0's and 1's corresponds to "unsatisfiable" if it is a root,...
235 views

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 ... 0answers 200 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 ... 0answers 105 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 ... 0answers 103 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 ... 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 ... 0answers 76 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}]... 0answers 328 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 ... 0answers 57 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 ... 0answers 105 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 ... 0answers 189 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 ... 0answers 114 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 ... 0answers 151 views ### What are some efficient algorithms for finding the solutions to a quadratic multivariate polynomial? Based on this question, there's an efficient algorithm to determine whether a quadratic multivariate polynomial has a root. What are some algorithms to enumerate these solutions? I'm interested in ... 0answers 103 views ### Geometry on a space of polynomial functions I am considering some geometric concepts in a space of functions.But I am not sure the concept I consider is already defined in some references. Let P_{1},...,P_{N}:\mathbb{F}_{2}^{n}\rightarrow \... 0answers 267 views ### Some problems involving polynomials of public and private variables over GF(2). Suppose there are a set of low degree (less than some degree z) polynomials P_0, P_1, ..., P_k each of which is defined over two types of variables, red variables {v_r}_0, {v_r}_1, ..., {v_r}_n ... 0answers 86 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 ... 0answers 177 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 ... 0answers 99 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}=... 0answers 20 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 ... 0answers 57 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 ... 0answers 94 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 ... 0answers 332 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 ... 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 ... 0answers 62 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 ... 0answers 155 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 ... 0answers 71 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 ... 0answers 75 views ### Verifying the minimum degree of a geometric predicate Let F = (f_1, \ldots, f_n) be a sequence of multivariate polynomials f_i : \mathbb{R}^d \to \mathbb{R}, and g : \{0,1\}^n \to \{0,1\} a boolean function. Say the composition$$h(x)=g(f_1(x)>...
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 ...
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 ...