Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$).

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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