<p>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$.</p>

<p>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$.</p>

<p>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}$?)</p>

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

<p>Any previous results or ideas would help. Thanks!</p>

CC BY-SA 3.0
2016-01-05T23:40:18.503Z
Isn't your condition equivalent to $C_{\emptyset}=0$ and $C_{\{i\}}=1$ for all $i$?
domotorp
CC BY-SA 3.0
2016-01-06T05:48:40.113Z
Yes, you are right~!
Zihan Tan
CC BY-SA 3.0
2016-01-07T22:02:56.660Z
The parity function is fully sensitive at zero, and has only 2 non-zero terms.
Igor Shinkar
CC BY-SA 3.0
2016-01-08T02:05:29.043Z
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.
Zihan Tan
CC BY-SA 3.0
2016-01-12T13:14:17.617Z
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.
chazisop
CC BY-SA 3.0
2016-01-13T07:13:19.287Z
Sorry but I think this multilinear expression is quite different from Fourier one. For example the function $f(x)=\wedge_{i=1}^n x_i=\mathbb{1}_{\vec{x}=\vec{1}}$ can be represented as $f(x)=\prod_{i=1}^n x_i$ when it is $\{0,1\}\to \{0,1\}$, but would be quite complicated if transferred into Fourier representation. And therefore the number of nonzero terms (the sparsity in the representation) would also be different.
Zihan Tan
<cc.complexity-theory><communication-complexity>
Lower Bound for Nonzero Terms of a Polynomial Fully Sensitive at 0
Zihan Tan
# Lower Bound for Nonzero Terms of a Polynomial Fully Sensitive at 0

(Asked by: username_0 on 2016-01-05)

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!

**Tags:** cc.complexity-theory, communication-complexity

> **Comments:**
> **username_1**: Isn't your condition equivalent to $C_{\emptyset}=0$ and $C_{\{i\}}=1$ for all $i$?  
> **username_0**: Yes, you are right~!  
> **username_2**: The parity function is fully sensitive at zero, and has only 2 non-zero terms.  
> **username_0**: 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.  
> **username_3**: 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.  
> **username_0**: Sorry but I think this multilinear expression is quite different from Fourier one. For example the function $f(x)=\wedge_{i=1}^n x_i=\mathbb{1}_{\vec{x}=\vec{1}}$ can be represented as $f(x)=\prod_{i=1}^n x_i$ when it is $\{0,1\}\to \{0,1\}$, but would be quite complicated if transferred into Fourier representation. And therefore the number of nonzero terms (the sparsity in the representation) would also be different.  

---

## 0 answers

