4
$\begingroup$

Given boolean $f(\Bbb x)$, with $\Bbb x\in\{0,1\}^n$, what are good upper/lower bounds, in terms of $|f^{-1}(0)|$, for minimum $deg(p(\Bbb x))$ of a real polynomial satisfying $p(\Bbb x)=f(\Bbb x)$?

$\endgroup$
  • $\begingroup$ There is not any upper bound, extra degree does not restrict the class of functions. For lower bound, is min deg a monotone function in the number of zeros? $\endgroup$ – Kaveh Nov 15 '14 at 21:12
  • $\begingroup$ Why is there no upper bound? I am just looking for two numbers $\theta_f(|f^{-1}(0)|)$ and $\psi_f(|f^{-1}(0)|)$ such that $\theta_f(|f^{-1}(0)|)\leq \mbox{minimum }deg(p(x))\leq\psi_f(|f^{-1}(0)|)$. $\endgroup$ – ASF Nov 15 '14 at 21:31
  • $\begingroup$ Originally the question asked for upper bound on the degree of any polynomial representing f and that one does not have an upper bound. $\endgroup$ – Kaveh Nov 15 '14 at 23:03
4
$\begingroup$

One relevant result is that if $\deg f = d$ then $2^d\hat{f}(S)$ is an integer for all $S$ (see for example exercise 12(b) here). In particular, $2^d\hat{f}(\emptyset) = 2^{d-n}|f^{-1}(1)|$ is an integer, and so $|f^{-1}(0)|$ is a multiple of $2^{n-d}$. This gives a lower bound on $d$ given $|f^{-1}(0)|$, which is tight for an AND of $d$ variables.

In terms of corresponding upper bounds you can't expect much, since there are balanced functions of maximal degree (parity for example). Moreover, there are functions with $|f^{-1}(0)| = 2^{n-k}$ of maximal degree for all $1 \leq k \leq n$, for example parity on $n-k+1$ variables ORed with $k-1$ variables; you can probably be a bit more cunning and construct a function of maximal degree for any given $0 < |f^{-1}(0)| < 2^n$. However, if $|f^{-1}(0)| \in \{0,2^n\}$ then the function is constant.

$\endgroup$
  • $\begingroup$ I think you missed the reference for exercise 12(b). Do you think this problem can be approached by sensitivity technique (say if one can pick the zero set structurally)? $\endgroup$ – ASF Nov 16 '14 at 7:53
  • $\begingroup$ Added the reference. If you know more then you can probably say more, but this is a very open-ended direction, and I'm not aware of anything of that sort. $\endgroup$ – Yuval Filmus Nov 16 '14 at 15:21

Your Answer

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

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