In Nisan and Szegedy's 1994 paper "On the degree of boolean functions as real polynomials"[1] Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\,\tfrac16\mathrm{bs}(f)\,}$? It clearly works for $\deg(f)$ and only this portion is shown in Jukna's book [2, Theorem 14.11]. Why does the proof work for $\widetilde{deg(f)}$?

Here $f$ is boolean function, $\widetilde{\deg(f)}$ is the $\tfrac13$-approximation degree of $f$, $\deg(f)$ is real degree of $f$ and $\mathrm{bs}(f)$ is block sensitivity of $f$.

[1] Noam Nisan and Mario Szegedy, "On the degree of boolean functions as real polynomials". Computational Complexity 4(4):301–313, 1994 (SpringerLink)
[2] Stasys Jukna, Boolean Function Complexity. Volume 27 of Algorithms and Combinatorics, Springer, 2012. (Homepage)

  • 1
    $\begingroup$ Turbo, I added full citations to the paper and book. I think I got the right one of Jutka's books but please fix it if I didn't! Either way, flag this comment as obsolete once you've dealt with it. $\endgroup$ – David Richerby Jan 7 '15 at 14:05

If you believe Lemma 3.8 for $\deg f$, you should also believe it for $\widetilde{\deg} f$. An earlier lemma states that if $f$ is a Boolean function on $n$ variables such that $f(\mathbf{0}) = 0$ and $f(\mathbf{x})=1$ for all $|\mathbf{x}|=1$ then $\deg f \geq \sqrt{n/2}$ and $\widetilde{\deg} f \geq \sqrt{n/6}$. Applying the first part of this lemma, we conclude the first part of Lemma 3.8, namely $\deg f \geq \sqrt{\operatorname{bs}(f)/2}$. Applying the second part of this lemma, we conclude the second part of Lemma 3.8, namely $\widetilde{\deg} f \geq \sqrt{\operatorname{bs}(f)/6}$.

| cite | improve this answer | |
  • $\begingroup$ Yes. But if you notice, you pass in only $f'$ from lemma 3.8 to the previous lemma. So it proves something on $\widetilde{deg(f')}$. How does it transfer to $\widetilde{deg(f)}$? $\endgroup$ – 1.. Jan 7 '15 at 19:23
  • $\begingroup$ @Turbo I believe it's within your powers to answer these questions yourself. The proof does work. Still, here are some hints. Just like $\deg f' \leq \deg f$, also $\widetilde{\deg} f' \leq \widetilde{\deg} f$. Regarding symmetry, the proof of the earlier lemma goes around this issue by symmetrizing the function. $\endgroup$ – Yuval Filmus Jan 7 '15 at 19:41
  • $\begingroup$ Ok. I will spend some time understanding $\widetilde{deg(f')}$ and $\widetilde{deg(f)}$. So you pass approximating polynomial to the previous lemma when you use widetilde instead of the eact polynomial? (But the function $f'$ now is not $0-1$ that is where I was confused). I will try to sink this in much more carefully. $\endgroup$ – 1.. Jan 7 '15 at 19:47
  • $\begingroup$ See if you can answer this yourself. Don't be lazy! $\endgroup$ – Yuval Filmus Jan 7 '15 at 19:49
  • $\begingroup$ $x_1x_2$ with $x_1$ replaced by $(1+y_1)$ yields $x_2+y_1x_2$ which is not symmetric while $x_1x_2$ was symmetric. $\endgroup$ – 1.. Jan 8 '15 at 4:41

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.