<p>Not sure if the notation I'm using here is standard or not. I'm going over class notes and I'm stumped over an exercise given: Show that $deg(f) = n \iff PI(f) \neq 0$.</p>

<p>Here $f$ is a boolean function on $n$ variables. $PI(f) = \sum\limits_{x \in f^{-1}(0)} (-1)^{w(x)}$. $w(x)$ is the number of bits = 1 in the input $x$. $deg(f)$ is the minimum degree of any polynomial representation of $f$. </p>

<p>This implies a sufficient condition that $f$ is evasive is $PI(f) \neq 0$. Thank you in advance for your help.</p>

CC BY-SA 3.0
2012-01-23T20:44:13.910Z
If you are asking about homework exercise, then this may not be the best place to ask your question. This site welcomes *research-level* questions. Please see the [FAQ](http://cstheory.stackexchange.com/faq) for more information on what is meant by "research-level" and for alternative places to ask your question. If after reading the [FAQ](http://cstheory.stackexchange.com/faq) you still feel that this is the appropriate venue for your question, perhaps you would like to rephrase it so that it doesn't sound like you are asking about a homework exercise.
Joe
CC BY-SA 3.0
2012-01-23T21:02:50.683Z
This isn't really a homework exercise. It was from a graduate level course, I'm prepping for my oral exam, it was a lemma from class who's proof was ommited as (exercise). Sorry if this isn't the correct place for it.
OpenCovering
CC BY-SA 3.0
2012-01-24T14:31:07.060Z
I don’t think the exercise is correct. Let $f(x,y)=x+y$: then $\deg(f)=1<2=n$, but $\mathrm{PI}(f)=2\ne0$.
Emil Jeřábek
CC BY-SA 3.0
2012-01-24T16:36:12.677Z
Lemma 4 in http://www.cs.uiuc.edu/~jeffe/teaching/497/05-evasive.pdf tells you that $\mathrm{PI}(f)\ne0$ is a *sufficient* condition for evasiveness, but not necessary.
Emil Jeřábek
CC BY-SA 3.0
2012-01-24T19:25:24.093Z
Rewrite $PI(f) = - \sum_{x \in \{0,1\}^n} [(-1)^{w(x)} \cdot f(x)]$ and show that this is 0 for every real function $f$ of degree less than $n$.
Noam
CC BY-SA 3.0
2012-01-24T20:18:56.110Z
@Emil, you're right about it being sufficient, not necessary (it follows from the fact that $deg(f) \leq D(f)$ where $D(f)$ is minimum depth of any decision tree for $f$). I'm assuming here that $f:\{0,1\}^n \rightarrow \{0,1\}$, so the counter example doesn't work. Noam's trick solves this problem, thanks!
OpenCovering
CC BY-SA 3.0
2012-01-24T20:22:38.880Z
Also, how do I mark this question as solved?
OpenCovering
CC BY-SA 3.0
2012-01-25T12:20:23.040Z
The counterexample is $f\colon\{0,1\}^2\to\{0,1\}$ (the addition is in the $2$-element field, of course, i.e., parity). $f^{-1}(0)=\{(0,0),(1,1)\}$, so $PI(f)=(-1)^0+(-1)^2=2$. What am I missing?
Emil Jeřábek
CC BY-SA 3.0
2012-01-25T12:27:24.183Z
Oh, I see: when you say “polynomial representation” of a Boolean function, you mean a polynomial over the reals, not over the Boolean ring?
Emil Jeřábek
CC BY-SA 3.0
2012-01-25T15:46:18.883Z
@OpenCovering, post your solution as an answer, and accept it.
Kaveh
<cc.complexity-theory><co.combinatorics><circuit-complexity><boolean-functions><fourier-analysis>
How to prove deg(f) = n iff the parity imbalance of f is non-zero?
OpenCovering
# How to prove deg(f) = n iff the parity imbalance of f is non-zero?

(Asked by: username_0 on 2012-01-23)

Not sure if the notation I'm using here is standard or not. I'm going over class notes and I'm stumped over an exercise given: Show that $deg(f) = n \iff PI(f) \neq 0$.

Here $f$ is a boolean function on $n$ variables. $PI(f) = \sum\limits\_{x \in f^{-1}(0)} (-1)^{w(x)}$. $w(x)$ is the number of bits = 1 in the input $x$. $deg(f)$ is the minimum degree of any polynomial representation of $f$.

This implies a sufficient condition that $f$ is evasive is $PI(f) \neq 0$. Thank you in advance for your help.

**Tags:** cc.complexity-theory, co.combinatorics, circuit-complexity, boolean-functions, fourier-analysis

> **Comments:**
> **username_1**: If you are asking about homework exercise, then this may not be the best place to ask your question. This site welcomes *research-level* questions. Please see the [FAQ](http://cstheory.stackexchange.com/faq) for more information on what is meant by "research-level" and for alternative places to ask your question. If after reading the [FAQ](http://cstheory.stackexchange.com/faq) you still feel that this is the appropriate venue for your question, perhaps you would like to rephrase it so that it doesn't sound like you are asking about a homework exercise.  
> **username_0**: This isn't really a homework exercise. It was from a graduate level course, I'm prepping for my oral exam, it was a lemma from class who's proof was ommited as (exercise). Sorry if this isn't the correct place for it.  
> **username_2**: I don’t think the exercise is correct. Let $f(x,y)=x+y$: then $\deg(f)=1<2=n$, but $\mathrm{PI}(f)=2\ne0$.  
> **username_2**: Lemma 4 in http://www.cs.uiuc.edu/~jeffe/teaching/497/05-evasive.pdf tells you that $\mathrm{PI}(f)\ne0$ is a *sufficient* condition for evasiveness, but not necessary.  
> **username_3**: Rewrite $PI(f) = - \sum_{x \in \{0,1\}^n} [(-1)^{w(x)} \cdot f(x)]$ and show that this is 0 for every real function $f$ of degree less than $n$.  
> **username_0**: @Emil, you're right about it being sufficient, not necessary (it follows from the fact that $deg(f) \leq D(f)$ where $D(f)$ is minimum depth of any decision tree for $f$). I'm assuming here that $f:\{0,1\}^n \rightarrow \{0,1\}$, so the counter example doesn't work. username_3's trick solves this problem, thanks!  
> **username_0**: Also, how do I mark this question as solved?  
> **username_2**: The counterexample is $f\colon\{0,1\}^2\to\{0,1\}$ (the addition is in the $2$-element field, of course, i.e., parity). $f^{-1}(0)=\{(0,0),(1,1)\}$, so $PI(f)=(-1)^0+(-1)^2=2$. What am I missing?  
> **username_2**: Oh, I see: when you say “polynomial representation” of a Boolean function, you mean a polynomial over the reals, not over the Boolean ring?  
> **username_4**: @username_0, post your solution as an answer, and accept it.  

---

## 0 answers

