In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric boolean (partial and total) functions in terms of a quantity denoted $\Gamma$:
Theorem (Paturi): Let $f$ be any non-constant symmetric function, and denote $f_k=f(x)$ when $|x|=k$ (i.e. the hamming weight of $x$ is $k$). The approximate degree of $f$, denoted $\widetilde{deg}(f)$, is $\Theta(\sqrt{n(n-\Gamma(f))})$, where $\Gamma(f)=\min\{|2k-n+1|:f_k\neq f_{k+1}\text{ and } 0\leq k\leq n-1\}$
Now let $Thr_t(x)$ be the threshold function, i.e. $Thr_t(x)=1$ if $x\geq t$. In this paper (cf. section 8, page 15) says that $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$.
Observe that for the threshold function we have $\Gamma(Thr_t)=|2(t-1)-n+1|$, because when $|x|=t-1$ the function changes from 0 to 1. Am I right?
If I apply directly Paturi's theorem to this value of $\Gamma$, I don't get the lower bound on the threshold function reported in other papers. Is the value of $\Gamma(Thr_t)$ above correct? What am I missing?
Edit: I also tried computing the quantum adversary lower bound for threshold. First, let's review the theorem.
Theorem (Unweighted Quantum Adversary): Let $f$ be a partial boolean function, and let $A\subseteq f^{-1}(0)$ and $B\subseteq f^{-1}(1)$ be subset of (hard) inputs. Let $R\subseteq A\times B$ be a relation, and set $R_i=\{(x,y)\in R : x_i\neq y_i\}$ for each $1\leq i \leq n$. Let $m,m'$ denote the minimal number of 1s in any row and any column in relation $R$ respectively, and let $\ell,\ell'$ denote the maximal number of ones in any row and column in any of the relations $R_i$ respectively. Then $Q_2(f)=\Omega(\sqrt{\frac{m m'}{\ell \ell'}})$.
If I define $B$ as the set of all inputs with the number of 1s greater than or equal to $t$, and $A$ all the inputs with 1s strictly less than $t$, I get (after some algebra) that $\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$.
So still I'm not getting the same lower bounds reported in other papers. Now, let's compare these bounds. The figure below shows for $n=200$ and without the square roots, a comparison between Paturi's theorem bound (blue), adversary bound (red), and the reported bound from other papers (green).
My questions are:
1- How do I get the bound reported in other papers?
2- You can see from the figure, that the reported lower bound (green) also lower bounds Paturi's bound and the adversary bound. Isn't that weakening the "real" lower bound? For example, if Paturi says that for all symmetric functions we have this bound, then how can you get a matching upper bound for quantum counting ($\sqrt{(t+1)(n-t+1)}$)? Isn't that upper bound violating Paturi's theorem?
