9
$\begingroup$

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

enter image description here

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?

$\endgroup$
  • $\begingroup$ You're missing the absolute value in the calculation for $\Gamma(Thr_t)$ (this seems to be too small a change for an edit). $\endgroup$ – Hartmut Klauck Feb 22 '11 at 5:55
  • $\begingroup$ 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 :) $\endgroup$ – Marc Bury Feb 22 '11 at 10:18
  • $\begingroup$ yeap, it seems like an approximation (here is the plot wolframalpha.com/input/…). 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? $\endgroup$ – Marcos Villagra Feb 22 '11 at 12:34
  • 1
    $\begingroup$ 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? $\endgroup$ – Marc Bury Feb 22 '11 at 12:49
  • 1
    $\begingroup$ It is the same up to a constant. $\endgroup$ – Kristoffer Arnsfelt Hansen Mar 3 '11 at 10:15
6
+50
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Marcos Villagra Mar 6 '11 at 3:20
  • $\begingroup$ 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. $\endgroup$ – Marcos Villagra Mar 6 '11 at 3:25

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.