Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$).

Consider the following high-degree extension of $OR(x)$: Choose a prime $q\in[n^2,2n^2]$ and let $p:\mathbb{F}_q^n\to\mathbb{F}_q$ such that $$p(x_1,\ldots,x_n)=1-(1-x_1)\cdot(1-x_2)\cdot\ldots\cdot(1-x_n)$$ Note that $p$ is a polynomial of degree $n$.

Now, lets call a polynomial $p':\mathbb{F}_q^n\to\mathbb{F}_q$ an $\epsilon$-approximation of $p$ if

$$\Pr_{x\in\mathbb{F}_q^n}[p(x)\neq p'(x)]<\epsilon$$

Is there a way to construct a low-degree polynomial which approximates $p$ (the high degree extension of $OR$) with $\epsilon<\frac{1}{3}$ ?

Just to clarify, by low-degree I mean a constant degree (which is not a function of $n$).


No. In fact, there is no such polynomial of degree smaller than $n$. Otherwise, $f=p-p'$ is a nonzero polynomial of degree at most $n$, hence

$$\Pr_{x\in\mathbb F_q^n}(p(x)=p'(x))=\Pr_{x\in\mathbb F_q^n}(f(x)=0)\le\frac nq<1-\epsilon$$

by the Schwartz–Zippel lemma.

  • $\begingroup$ So this also holds for any $\epsilon < 1$: no such polynomial as soon as $n > 1/(1-\epsilon)$. $\endgroup$ – Pietro Majer Oct 11 '11 at 16:10

Your Answer

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