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&nbsp;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&nbsp;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&ndash;313, 1994 (SpringerLink)
[2] Stasys Jukna, Boolean Function Complexity. Volume 27 of Algorithms and Combinatorics, Springer, 2012. (Homepage)
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}$.