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

2 Answers 2

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

0

What is the reason for selecting $q$ in that range $[n,2n]$? As in the case of the previous question(s) I think that $q=2$ is simplest. I mean, the values of OR-function are binary, the inputs are binary???

If we go with $q=2$ as before, then the theory of the Reed-Muller codes gives you the following answer: a polynomial $p\in GF(2][x_1,\ldots,x_n]$ of degree $k$ yielding a non-constant function takes the value $0$ at least $2^{n-k}$ times, and the set of zeros can be any coset of any $(n-k)$-dimensional subspace. This is equivalent to saying that the minimum Hamming distance of the Reed-Muller code $R(k,n)$ is $2^{n-k}$ and that all the minimum weight codewords have supports that are cosets of a subspace of dimension $n-k$. These facts can be found in e.g. MacWilliams & Sloane.

Therefore a polynomial of degree $k$ makes at least $2^{n-k}-1$ errors when estimating $OR(x_1,x_2,\ldots,x_n)$. So the lowest possible error probability is $(2^{n-k}-1)/2^n=2^{-k}-2^{-n}$. This is attained by e.g. the polynomial $$ p=1-(1-x_1)(1-x_2)\cdots (1-x_k), $$ and the available variation comes from replacing the $x_i$:s with binary linear combinations of them. So to get error probabilities close to $2^{-n}$ (= the smallest non-zero error probability) I'm afraid you must let $k$ grow.

I don't know the answer, if we use polynomials with coefficients from a bigger field. I very much doubt that it would help, but I may be wrong. Sorry, I seem to be answering the wrong questions today :-)

  • 0
    No, in this case I'm actually interested in the case of a field which is larger than $n$. I'm looking for a field with more elements than the amount of roots of the polynomial, which maintain an error rate of say - less than 1/2.2011-10-11
  • 0
    thanks for the Reed-Muller perspective though, it really made me understand the problem better.2011-10-12