<p>This does not directly answer your question, but if $f$ is $n$-variate, and is known to have partial degrees at most $D$ and at most $T$ terms, and $\mathbb{F}$ is known to contain an element $\omega$ of multiplicative order exceeding $D$, then we cannot have $f(\omega^i, \dots, \omega^i)=0$ for $i=0,1,\dots,2T-1$ by Prony's method / BCH decoding / Ben-Or Tiwari algorithm.</p>

<p>Zippel calls your problem the zero avoidance problem.</p>

<p>See: <a href="http://www.sciencedirect.com/science/article/pii/S0747717108800181" rel="nofollow">Interpolating polynomials from their values.</a></p>

CC BY-SA 3.0
2016-01-13T20:47:55.797Z
2016-01-13T20:47:55.797Z
user41530
<p>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 <strong>deterministically</strong> find another point $X' \neq X$, such that $P(X') \neq 0$.</p>

<p>Basically, it is a standard Polynomial identity testing with only one new twist: we know that the solution exists. You can say that it is in some sense problem from $FRP \cap PPP$ (this is very informal statement, I am not sure that this problem is in $PPP$, but it has the same flavor).  </p>

<p>I would be glad if someone can point to some positive or negative results about this problem.</p>

CC BY-SA 3.0
2016-01-12T01:44:01.583Z
How low is "low degree"?
Denis Pankratov
CC BY-SA 3.0
2016-01-12T02:04:22.613Z
Let's say that total degree is bounded by some polynomial.
ivmihajlin
<cc.complexity-theory><cr.crypto-security><polynomials><search-problem><finite-fields>
How to find a non-zero point of a non-zero polynomial of low degree?
ivmihajlin
# How to find a non-zero point of a non-zero polynomial of low degree?

(Asked by: username_0 on 2016-01-11)

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 **deterministically** find another point $X' \neq X$, such that $P(X') \neq 0$.

Basically, it is a standard Polynomial identity testing with only one new twist: we know that the solution exists. You can say that it is in some sense problem from $FRP \cap PPP$ (this is very informal statement, I am not sure that this problem is in $PPP$, but it has the same flavor).

I would be glad if someone can point to some positive or negative results about this problem.

**Tags:** cc.complexity-theory, cr.crypto-security, polynomials, search-problem, finite-fields
> **Comments:**
> **username_1**: How low is "low degree"?  
> **username_0**: Let's say that total degree is bounded by some polynomial.  

---

## 1 answers

### Answer by username_2 on 2016-01-13. Score: 2

This does not directly answer your question, but if $f$ is $n$-variate, and is known to have partial degrees at most $D$ and at most $T$ terms, and $\mathbb{F}$ is known to contain an element $\omega$ of multiplicative order exceeding $D$, then we cannot have $f(\omega^i, \dots, \omega^i)=0$ for $i=0,1,\dots,2T-1$ by Prony's method / BCH decoding / Ben-Or Tiwari algorithm.

Zippel calls your problem the zero avoidance problem.

See: [Interpolating polynomials from their values.](http://www.sciencedirect.com/science/article/pii/S0747717108800181)


---

