6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How low is "low degree"? $\endgroup$ – Denis Pankratov Jan 12 '16 at 1:44
  • $\begingroup$ Let's say that total degree is bounded by some polynomial. $\endgroup$ – ivmihajlin Jan 12 '16 at 2:04
2
$\begingroup$

If ​ (ceil(degree/n))+1 ​ is "large", then there doesn't actually need to be such an X$\hspace{.02 in}$'.
$\Bigg(\hspace{-0.08 in}$The polynomial can be $\;\;\; \displaystyle\prod_{i\hspace{.02 in}\in \hspace{.02 in}\text{coordinates}} \: \left(\displaystyle\prod_{c\hspace{.02 in}\in (\mathbb{F}\hspace{.03 in}-\{0\})} (x_{\hspace{.02 in}i}-c)\hspace{-0.07 in}\right) \;\;\;$ and X can be the origin.$\hspace{-0.08 in}\Bigg)$

If "large" means larger than 1 plus [the minimum over the variables of the degree in that variable], then there's a uniform NC$^0$ algorithm that will, with no access to the polynomial, with neither
bit operations nor field operations nor equality tests on field elements ($\hspace{.03 in}$just copying them and
moving them around), output a polynomial-length list of elements of $\mathbb{F}^n$ such that at least one
of those elements is such an X'. ​ (When B is an upper bound on the bracketed expression from
the previous sentence, the algorithm will have B+2 distinct hard-coded field elements and output the ​ n$\cdot$(B+2) ​ results of replacing one of X's coordinates with one of the B+2 field elements.)

Thus, you need to either consider fields of "intermediate" size, or allow polynomials of
large (superpolynomial) degree. ​ (Arithmetic circuits can easily have exponential degree.)



A problem that's closer to canonical for ​ FRP ∩ PPP ​ (and is actually obviously in PPP) is


Input: ​ ​ ​ A (circuit encoding a) function ​ f : {0,1}n+1 -> {0,1}n
and a (circuit encoding a) function ​ g : {0,1}n -> {0,1}n+1

Correct Outputs: ​ ​ ​ elements x of {0,1}n+1 such that ​ g(f(x)) ≠ x


.

$\endgroup$
  • 2
    $\begingroup$ It seems as there's some problem with the formatting but I'm not sure what you were aiming for. Can you make an edit to make your answer easier to read? $\endgroup$ – chazisop Jan 12 '16 at 12:49
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.