# Lower bound on approximation degree in Nisan-Szegedy

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)

• 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. Jan 7, 2015 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}$.
• 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)}$? Jan 7, 2015 at 19:23
• @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. Jan 7, 2015 at 19:41
• 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. Jan 7, 2015 at 19:47
• $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. Jan 8, 2015 at 4:41