Límites inferiores en la función Umbral

En la complejidad del árbol de decisión de una función booleana, un método de límite inferior muy conocido es encontrar un polinomio (aproximado) que represente la función. Paturi dio una caracterización para funciones booleanas simétricas (parciales y totales) en términos de una cantidad denotada :$\Gamma$

Teorema ( Paturi ): Sea $f$ cualquier función simétrica no constante, y denote $f_k=f(x)$ cuando $|x|=k$ (es decir, el peso de hamming de $x$ es $k$ ). El grado aproximado de $f$ , denotado $\widetilde{deg}(f)$ , es $\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\}$

Ahora deje que sea ​​la función umbral, es decir, Thr_t (x) = 1 si x \ geq t . En este documento (véase la sección 8, página 15) dice que \ widetilde {deg} (f) = \ sqrt {(t + 1) (N-t + 1)} .$Thr_t(x)$$Thr_t(x)=1$$x\geq t$$\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$

Observe que para la función de umbral tenemos $\Gamma(Thr_t)=|2(t-1)-n+1|$, porque cuando $|x|=t-1$ la función cambia de 0 a 1. ¿Estoy en lo cierto?

Si aplico directamente el teorema de Paturi a este valor de $\Gamma$ , no obtengo el límite inferior en la función de umbral que se informa en otros documentos. ¿Es correcto el valor de $\Gamma(Thr_t)$ anterior? ¿Qué me estoy perdiendo?

Editar: también intenté calcular el límite inferior del adversario cuántico para el umbral. Primero, repasemos el teorema.

Teorema (Adversario cuántico no ponderado): Sea una función booleana parcial y deje que y sean subconjuntos de entradas (duras). Sea una relación, y establezca para cada . Supongamos que denota el número mínimo de 1s en cualquier fila y columna en relación respectivamente, y que denota el número máximo de unidades en cualquier fila y columna en cualquiera de las relaciones respectivamente. Entonces .$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'}})$

Si defino como el conjunto de todas las entradas con el número de 1s mayor o igual que , y todas las entradas con 1s estrictamente menores que , obtengo (después de un poco de álgebra) que .$B$$t$$A$$t$$\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$

Entonces todavía no obtengo los mismos límites inferiores reportados en otros documentos. Ahora, comparemos estos límites. La siguiente figura muestra para y sin las raíces cuadradas, una comparación entre el límite del teorema de Paturi (azul), el límite del adversario (rojo) y el límite informado de otros documentos (verde).$n=200$

Mis preguntas son:

1- ¿Cómo obtengo el límite informado en otros documentos?

2- Se puede ver en la figura que el límite inferior reportado (verde) también limita el límite de Paturi y el límite del adversario. ¿No es eso debilitar el límite inferior "real"? Por ejemplo, si Paturi dice que para todas las funciones simétricas tenemos este límite, ¿cómo puede obtener un límite superior coincidente para el conteo cuántico ( )? ¿No es ese límite superior violar el teorema de Paturi?$\sqrt{(t+1)(n-t+1)}$

No sé cómo puede obtener o ver el límite de del límite original pero aquí está la prueba de que estos límites son asintóticamente iguales hasta un factor constante:$\sqrt{(t+1)(n-t+1)}$$\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$

Primero vea que (excluyo porque la función de umbral es siempre ) $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 ) y 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)$

Ahora debe calcular el valor máximo (de acuerdo con dentro de los intervalos definidos) de las fracciones f 1 ( t ) / g ( t ) , f 2 ( t ) / g ( t ) , g ( t ) / f 1 ( t ) y 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)$. Puede hacer esto con cálculo diferencial o aproximación con la ayuda del gráfico (con 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$

Esto le da y también el resultado deseado

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

¿Hay una manera más fácil de ver / obtener este resultado?