Limites inferiores na função Threshold

Na complexidade da árvore de decisão de uma função booleana, um método de limite inferior muito bem conhecido é encontrar um polinômio (aproximado) que represente a função. Paturi deu uma caracterização para funções booleanas simétricas (parciais e totais) em termos de uma quantidade indicada $\Gamma$ :

Teorema ( Paturi ): Seja $f$ qualquer função simétrica não constante e denote $f_k=f(x)$ quando $|x|=k$ (ou seja, o peso hamming de é ). O grau aproximado de , denotado , é , onde$x$$k$$f$$\widetilde{deg}(f)$$\Theta(\sqrt{n(n-\Gamma(f))})$$\Gamma(f)=\min\{|2k-n+1|:f_k\neq f_{k+1}\text{ and } 0\leq k\leq n-1\}$

Agora deixe $Thr_t(x)$ ser a função de limite, ou seja, $Thr_t(x)=1$ se $x\geq t$ . Neste artigo (cf. seção 8, página 15) diz que $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$ .

Observe que, para a função de limite, temos $\Gamma(Thr_t)=|2(t-1)-n+1|$, porque quando $|x|=t-1$ a função muda de 0 para 1. Estou certo?

Se eu aplicar diretamente o teorema de Paturi a esse valor de $\Gamma$ , não obtenho o limite inferior na função de limite relatada em outros trabalhos. O valor de $\Gamma(Thr_t)$ acima está correto? o que estou perdendo?

Edit: Eu também tentei calcular o limite inferior do adversário quântico para o limiar. Primeiro, vamos revisar o teorema.

Teorema (Adversário Quântico Não Ponderado): Seja uma função booleana parcial e seja e seja um subconjunto de entradas (rígidas). Seja uma relação e defina para cada . Deixe denotar o número mínimo de 1s em qualquer linha e qualquer coluna em relação , respectivamente, e let denotar o número máximo de unidades em qualquer linha e coluna em qualquer uma das relações respectivamente. Então .Um ⊆ f - 1 ( 0 ) B ⊆ f - 1 ( 1 ) R ⊆ Um × B R i = { ( x , y ) ∈ R : x i ≠ y i } um ≤ i ≤ n m , m ' R ℓ , ℓ ' R I Q 2 ( f $f$$A\subseteq f^{-1}(0)$$B\subseteq f^{-1}(1)$$R\subseteq A\times B$$R_i=\{(x,y)\in R : x_i\neq y_i\}$$1\leq i \leq n$$m,m'$$R$$\ell,\ell'$$R_i$$Q_2(f)=\Omega(\sqrt{\frac{m m'}{\ell \ell'}})$

Se eu definir como o conjunto de todas as entradas com o número de 1s maior ou igual a , e todas as entradas com 1s estritamente menores que , obtenho (depois de alguma álgebra) que .$B$$t$$A$$t$$\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$

Ainda assim, não estou obtendo os mesmos limites inferiores relatados em outros trabalhos. Agora, vamos comparar esses limites. A figura abaixo mostra para e sem as raízes quadradas, uma comparação entre o limite do teorema de Paturi (azul), limite do adversário (vermelho) e o limite relatado de outros trabalhos (verde).$n=200$

Minhas perguntas são:

1- Como obtenho o limite relatado em outros trabalhos?

2- Você pode ver na figura que o limite inferior relatado (verde) também limita o limite de Paturi e o limite do adversário. Isso não está enfraquecendo o limite inferior "real"? Por exemplo, se Paturi diz que, para todas as funções simétricas, temos esse limite, como você pode obter um limite superior correspondente para a contagem quântica ( )? Esse limite superior não viola o teorema de Paturi?$\sqrt{(t+1)(n-t+1)}$

Eu não sei como você pode obter ou ver o limite de do limite original$\sqrt{(t+1)(n-t+1)}$ mas aqui está a prova de que esses limites são assintoticamente iguais até um fator constante:$\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$

Primeiro veja que (eu excluo porque a função de limite é sempre 1 ) n ( n - | ( 2 ( t - 1 ) - n + 1 | ) = { n ( 2 t - 1 ) 1 ≤ t ≤ n / 2 + 1 / 2 n ( 2 n - 2 t + 1 ) $t = 0$$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.$$

Definir , f 2 ( t ) = n ( 2 n - 2 t + 1 ) e g ( t ) = ( T + 1 ) ( n - T + 1 ) .$f_1(t) = n(2t-1)$$f_2(t) = n(2n-2t+1)$$g(t) = (t+1)(n-t+1)$

Agora você deve calcular o valor máximo (de acordo com dentro dos intervalos definidos) das frações f 1 ( t ) / g ( t ) , f 2 ( t ) / g ( t ) , g ( t ) / f 1 ( t ) e g ( t ) / f 2 ( t $t$$f_1(t)/g(t)$$f_2(t)/g(t)$$g(t)/f_1(t)$$g(t)/f_2(t)$. Você pode fazer isso com cálculo diferencial ou aproximação com a ajuda do gráfico (com suficientemente grande):$n$

$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$

$$n(n-\vert 2(t-1)-n-1\vert) = \Theta((t+1)(n-t+1))$$ $$\sqrt{n(n-\vert 2(t-1)-n-1 \vert)} = \Theta(\sqrt{(t+1)(n-t+1)}).$$

Existe uma maneira mais fácil de ver / obter esse resultado?