1
$\begingroup$

Let $f$ be a Boolean function.

Let $g$ be the minimum degree real polynomial that represents $f$ with degree $d$.

Let $g_{p}$ be the minimum degree $\Bbb F_p$ polynomial that represents $f$ with degree $d_p$.

Does $\exists p:d_p\leq d\leq d_p^c$ hold with some constant $c>0$?

$d_2\leq d\leq d_2^c$ does not hold with some constant $c>0$.

Counter example at $\Bbb F_2$.

$IP_n=\sum_{i=1}^nx_iy_i\bmod 2$ does have $d_2=2$, while $d=\Omega(n)$.

$\endgroup$
  • $\begingroup$ Did you try generalizing your example to other $p$? $\endgroup$ – Yuval Filmus Jan 31 '15 at 5:09
  • $\begingroup$ I tried for $IP_{n,p}=(\sum_{i=1}^nx_iy_i\mod p)\mod 2$, $\endgroup$ – T.... Jan 31 '15 at 5:50
  • $\begingroup$ Did you use the fact that mod 2 is a constant polynomial? E.g. $2x^2+2x$ when $p=3$. $\endgroup$ – Yuval Filmus Jan 31 '15 at 21:15
  • $\begingroup$ Interesting no I did not think of that. I just thought we have to interpolate at $p$ distinct terms instead of $n$ terms. $\endgroup$ – T.... Jan 31 '15 at 21:30

Your Answer

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

Browse other questions tagged or ask your own question.