Every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be uniquely represented as a multilinear polynomial $p=\sum_{S\subseteq [n]}c_S \chi_s$ where $\chi_s=\prod_{i\in S}x_i$.

A boolean function is fully-sensitive at $\vec{0}$ if $f(\vec{0})=0$ (wlog) and takes value $1$ on any input with hamming weight $1$.

Question: Is there any lower bound on the number of nonzero terms for such a polynomial(originated from a boolean function and fully-sensitive at $\vec{0}$?)

To the best of my knowledge, Noam Nisan and Avi Wigderson studied this type of function and proposed an example with degree $O(n^{log_3 2})$, which also suggested an upper bound of $2^{O(n^{\log_3 2})}$ on the number of nonzero terms, but what about the lower bounds? Besides, the character of "fully sensitive at $\vec{0}$" is indeed an embedding of Unique Disjoint Function, which also has results on lower bound on nonnegative ranks, etc. However, those results and ideas seem not directly applicable here.

Any previous results or ideas would help. Thanks!

  • $\begingroup$ Isn't your condition equivalent to $C_{\emptyset}=0$ and $C_{\{i\}}=1$ for all $i$? $\endgroup$ – domotorp Jan 5 '16 at 23:40
  • $\begingroup$ Yes, you are right~! $\endgroup$ – Zihan Tan Jan 6 '16 at 5:48
  • $\begingroup$ The parity function is fully sensitive at zero, and has only 2 non-zero terms. $\endgroup$ – Igor Shinkar Jan 7 '16 at 22:02
  • $\begingroup$ Oh probably not, since we require that the function be boolean. I think you mean $f=x_1+x_2$? Actually it should be written as $f=x_1+x_2-2x_1x_2$ in order to be boolean. $\endgroup$ – Zihan Tan Jan 8 '16 at 2:05
  • $\begingroup$ If you transform $0 -> 1$ and $1 -> -1$ and work with multiplication over {-1,1}, as it is common in Fourier analysis of Boolean functions, then parity can be represented by the single monomial $x_{1} \dots x_{n}$. It's clear that for the question to make sense, one needs to specify allowed operations (e.g. is addition mod 2 allowed?), i.e. the underlying model, as well as the representation used. $\endgroup$ – chazisop Jan 12 '16 at 13:14

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.