<p>I don't know how you can get or see the bound of $\sqrt{(t+1)(n-t+1)}$ from the original bound $\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$ but here is the proof that this bounds are asymptotically equal up to a constant factor:</p>

<p>First see that (I exclude $t = 0$ because the threshold function is always $1$)
$$ n(n-\vert (2(t-1) -n+1 \vert) = \left\lbrace 
\begin{array}{ll} 
n(2t-1) &amp; 1 \leq t \leq n/2+1/2\\
n(2n-2t+1) &amp; n/2+1/2 \leq t \leq n-1
\end{array} \right. $$</p>

<p>Define $f_1(t) = n(2t-1)$, $f_2(t) = n(2n-2t+1)$ and $g(t) = (t+1)(n-t+1)$.</p>

<p>Now you have to calculate the maximal value (according to $t$ within the defined intervalls) of the fractions $f_1(t)/g(t)$, $f_2(t)/g(t)$, $g(t)/f_1(t)$ and $g(t)/f_2(t)$. You can do this with differential calculus or approximation with the help of the graph (with $n$ large enough):</p>

<p>$f_1(t)/g(t) \leq f_1(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$</p>

<p>$f_2(t)/g(t) \leq f_2(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$</p>

<p>$g(t)/f_1(t) \leq g(1)/f_1(1) = \dfrac{2n}{n} = 2$</p>

<p>$g(t)/f_2(t) \leq g(n-1)/f_2(n-1) = \dfrac{n/2}{n/3} \leq 3/2$</p>

<p>This gives you 
$$n(n-\vert 2(t-1)-n-1\vert) = \Theta((t+1)(n-t+1))$$ 
and also the wanted result 
$$\sqrt{n(n-\vert 2(t-1)-n-1 \vert)} = \Theta(\sqrt{(t+1)(n-t+1)}).$$</p>

<p>Is there an easier way to see/get this result?</p>

CC BY-SA 2.5
2011-03-06T03:20:32.217Z
Yes, I think you are right. My impression is that the original authors knew about that lower bound because of some results like quantum couting. In quantum couting we have an upper bound of $\sqrt{(t+1)(n-t+1)}$, and by applying Paturi's theorem and the adversary bounds, they showed what you just showed here.
Marcos Villagra
CC BY-SA 2.5
2011-03-06T03:25:21.153Z
thanks for your efforts!! I think this is the answer. I'm more convinced now that maybe this is only way to get this result.
Marcos Villagra
CC BY-SA 2.5
2011-03-05T03:41:31.387Z
2011-03-05T03:41:31.387Z
Marc Bury
<p>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. <a href="http://portal.acm.org/citation.cfm?id=129758" rel="nofollow noreferrer">Paturi</a> gave a characterization for symmetric boolean (partial and total) functions in terms of a quantity denoted $\Gamma$:</p>

<blockquote>
  <p><strong>Theorem (<a href="http://portal.acm.org/citation.cfm?id=129758" rel="nofollow noreferrer">Paturi</a>):</strong> 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\}$</p>
</blockquote>

<p>Now let $Thr_t(x)$ be the threshold function, i.e. $Thr_t(x)=1$ if $x\geq t$. In this <a href="http://arxiv.org/abs/quant-ph/0509153" rel="nofollow noreferrer">paper</a> (cf. section 8, page 15) says that $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$.</p>

<p>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?</p>

<p>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?</p>

<p><strong>Edit:</strong> I also tried computing the quantum adversary lower bound for threshold. First, let's review the theorem.</p>

<blockquote>
  <p><strong>Theorem (Unweighted Quantum Adversary):</strong> 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'}})$.</p>
</blockquote>

<p>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})$.</p>

<p>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).</p>

<p><img src="https://i.sstatic.net/fj8c6.jpg" alt="enter image description here"></p>

<p>My questions are:</p>

<p>1- How do I get the bound reported in other papers?</p>

<p>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?</p>

CC BY-SA 2.5
2011-02-22T05:55:45.357Z
You're missing the absolute value in the calculation for $\Gamma(Thr_t)$ (this seems to be too small a change for an edit).
Hartmut Klauck
CC BY-SA 2.5
2011-02-22T10:18:13.163Z
I think you are right and it is a kind of approximation of the absolue value $\Gamma(Thr_t)=|2(t-1)-n+1|$ to get the degree mentioned in the paper. The plots of the functions let me suppose that :)
Marc Bury
CC BY-SA 2.5
2011-02-22T12:34:45.550Z
yeap, it seems like an approximation (here is the plot http://www.wolframalpha.com/input/?i=plot+100(100-abs(2(t-1)-100%2B1))+and+(t%2B1)(100-t%2B1)). And it lower bounds $\Gamma(Thr_t)$. If it is so, then why bother to do that? Why not just apply the resulting lower bound from Paturi's?
Marcos Villagra
CC BY-SA 2.5
2011-02-22T12:49:25.917Z
I suppose they want to avoid the absolue value function. They get an easier form of the function and avoid case-by-case analysis for any calculation. I'm interested in how they get this approximation out of the original function?
Marc Bury
CC BY-SA 2.5
2011-03-03T10:15:46.080Z
It is the same up to a constant.
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><quantum-computing><lower-bounds><boolean-functions><query-complexity>
Lower bounds on the Threshold function
Marcos Villagra
# Lower bounds on the Threshold function

(Asked by: username_0 on 2011-02-22)

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](http://portal.acm.org/citation.cfm?id=129758) gave a characterization for symmetric boolean (partial and total) functions in terms of a quantity denoted $\Gamma$:

> **Theorem ([Paturi](http://portal.acm.org/citation.cfm?id=129758)):** 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](http://arxiv.org/abs/quant-ph/0509153) (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).

![enter image description here](https://i.sstatic.net/fj8c6.jpg)

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?

**Tags:** cc.complexity-theory, quantum-computing, lower-bounds, boolean-functions, query-complexity

> **Comments:**
> **username_1**: You're missing the absolute value in the calculation for $\Gamma(Thr_t)$ (this seems to be too small a change for an edit).  
> **username_2**: I think you are right and it is a kind of approximation of the absolue value $\Gamma(Thr_t)=|2(t-1)-n+1|$ to get the degree mentioned in the paper. The plots of the functions let me suppose that :)  
> **username_0**: yeap, it seems like an approximation (here is the plot http://www.wolframalpha.com/input/?i=plot+100(100-abs(2(t-1)-100%2B1))+and+(t%2B1)(100-t%2B1)). And it lower bounds $\Gamma(Thr_t)$. If it is so, then why bother to do that? Why not just apply the resulting lower bound from Paturi's?  
> **username_2**: I suppose they want to avoid the absolue value function. They get an easier form of the function and avoid case-by-case analysis for any calculation. I'm interested in how they get this approximation out of the original function?  
> **username_3**: It is the same up to a constant.  

---

## 1 answers

### Answer by username_2 on 2011-03-05. Score: 6 | Accepted answer

I don't know how you can get or see the bound of $\sqrt{(t+1)(n-t+1)}$ from the original bound $\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$ but here is the proof that this bounds are asymptotically equal up to a constant factor:

First see that (I exclude $t = 0$ because the threshold function is always $1$)
$$ n(n-\vert (2(t-1) -n+1 \vert) = \left\lbrace
\begin{array}{ll}
n(2t-1) & 1 \leq t \leq n/2+1/2\\
n(2n-2t+1) & n/2+1/2 \leq t \leq n-1
\end{array} \right. $$

Define $f\_1(t) = n(2t-1)$, $f\_2(t) = n(2n-2t+1)$ and $g(t) = (t+1)(n-t+1)$.

Now you have to calculate the maximal value (according to $t$ within the defined intervalls) of the fractions $f\_1(t)/g(t)$, $f\_2(t)/g(t)$, $g(t)/f\_1(t)$ and $g(t)/f\_2(t)$. You can do this with differential calculus or approximation with the help of the graph (with $n$ large enough):

$f\_1(t)/g(t) \leq f\_1(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$

$f\_2(t)/g(t) \leq f\_2(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$

$g(t)/f\_1(t) \leq g(1)/f\_1(1) = \dfrac{2n}{n} = 2$

$g(t)/f\_2(t) \leq g(n-1)/f\_2(n-1) = \dfrac{n/2}{n/3} \leq 3/2$

This gives you
$$n(n-\vert 2(t-1)-n-1\vert) = \Theta((t+1)(n-t+1))$$
and also the wanted result
$$\sqrt{n(n-\vert 2(t-1)-n-1 \vert)} = \Theta(\sqrt{(t+1)(n-t+1)}).$$

Is there an easier way to see/get this result?

> **Comments:**
> **username_0**: Yes, I think you are right. My impression is that the original authors knew about that lower bound because of some results like quantum couting. In quantum couting we have an upper bound of $\sqrt{(t+1)(n-t+1)}$, and by applying Paturi's theorem and the adversary bounds, they showed what you just showed here.  
> **username_0**: thanks for your efforts!! I think this is the answer. I'm more convinced now that maybe this is only way to get this result.  

---

