1
$\begingroup$

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,2n]$ 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$. In [ Extending the logical-or function to a low degree polynomial over a finite field ] it was concluded that there is no polynomial of degree less than $n$ which extends the $OR$ function.

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$) well ?

Just to clarify, by low-degree I mean a constant degree (which is not a function of $n$). And by approximate well, I'm aiming for $\epsilon$ which is as small as possible (hopefully there is a degree vs. approxmation-ratio tradeoff).

1 Answers 1

1

Well, apparently this is not possible at all for any polynomial of degree less than $n$. To see why, consider \hat p=p-p'. If deg(p') then $\hat p$ is a non-zero polynomial of degree at most $n$. By the Schwartz-Zippel Lemma we get (assuming $q>n$, and $\epsilon<1$) \Pr_{x\in\mathbb{F}_q^n}[p(x)=p'(x)]=\Pr_{x\in\mathbb{F}_q^n}[\hat p(x)=0]\leq \frac{deg(\hat p)}{q}\leq \frac{n}{q}<1-\epsilon Thus \Pr_{x\in\mathbb{F}_q^n}[p(x)\neq p'(x)]\geq \epsilon Bummers...