Limites inférieures de la fonction de seuil

Dans la complexité de l'arbre de décision d'une fonction booléenne, une méthode de borne inférieure très connue est de trouver un polynôme (approximatif) qui représente la fonction. Paturi a donné une caractérisation des fonctions booléennes symétriques (partielles et totales) en termes de quantité notée $\Gamma$ :

Théorème ( Paturi ): Soit toute fonction symétrique non constante, et dénote lorsque (c'est-à-dire que le poids de hamming de est ). Le degré approximatif de , noté , est , où $f$ $f_k=f(x)$ $|x|=k$ $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\}$

Soit maintenant $Thr_t(x)$ la fonction seuil, ie $Thr_t(x)=1$ si $x\geq t$ . Dans cet article (cf. section 8, page 15) dit que $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$ .

Remarquez que pour la fonction de seuil, nous avons $\Gamma(Thr_t)=|2(t-1)-n+1|$ , car lorsque $|x|=t-1$ la fonction passe de 0 à 1. Ai-je raison?

Si j'applique directement le théorème de Paturi à cette valeur de $\Gamma$ , je n'obtiens pas la borne inférieure de la fonction de seuil rapportée dans d'autres articles. La valeur de $\Gamma(Thr_t)$ ci-dessus est-elle correcte? Qu'est-ce que je rate?

Edit: J'ai également essayé de calculer la limite inférieure de l'adversaire quantique pour le seuil. Tout d'abord, passons en revue le théorème.

Théorème (Adversaire Quantique Non Pondéré): Soit une fonction booléenne partielle, et que et soit un sous-ensemble d'entrées (dures). Soit une relation, et définissons pour chaque . Soit le nombre minimal de 1 dans n'importe quelle ligne et n'importe quelle colonne dans la relation respectivement, et soit le nombre maximal de uns dans n'importe quelle ligne et colonne dans n'importe laquelle des relations respectivement. Alors . $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 je définis comme l'ensemble de toutes les entrées avec le nombre de 1s supérieur ou égal à , et toutes les entrées avec 1s strictement inférieur à , j'obtiens (après une algèbre) que . $B$ $t$ $A$ $t$ $\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$

Donc, je n'obtiens toujours pas les mêmes limites inférieures rapportées dans d'autres articles. Maintenant, comparons ces limites. La figure ci-dessous montre pour et sans les racines carrées, une comparaison entre le théorème de Paturi lié (bleu), l'adversaire lié (rouge) et le rapporté rapporté d'autres papiers (vert). $n=200$

entrez la description de l'image ici

Mes questions sont:

1- Comment puis-je faire rapport de la limite dans d'autres articles?

2- Vous pouvez voir sur la figure, que la limite inférieure signalée (verte) limite également la limite de Paturi et la limite de l'adversaire. N'est-ce pas affaiblir la "vraie" borne inférieure? Par exemple, si Paturi dit que pour toutes les fonctions symétriques, nous avons cette limite, alors comment obtenir une limite supérieure correspondante pour le comptage quantique ( )? Cette limite supérieure ne viole-t-elle pas le théorème de Paturi? $\sqrt{(t+1)(n-t+1)}$

cc.complexity-theory quantum-computing lower-bounds boolean-functions query-complexity Marcos Villagra
la source

Vous la valeur absolue dans le calcul de (cela semble être un changement trop petit pour une modification).

Γ (T h r_{t})

$\Gamma(Thr_t)$

Hartmut Klauck

Je pense que vous avez raison et c'est une sorte d'approximation de la valeur absoluepour obtenir le diplôme mentionné dans le document. Les tracés des fonctions me laissent supposer que :)

Γ (T h r_{t}) = | 2 (t - 1) - n + 1 |

$\Gamma(Thr_t)=|2(t-1)-n+1|$

Marc Bury

oui, cela ressemble à une approximation (voici l'intrigue wolframalpha.com/input/… ). Et il limite inférieure . Si c'est le cas, pourquoi se donner la peine de le faire? Pourquoi ne pas simplement appliquer la borne inférieure résultante de celle de Paturi?

Γ (T h r_{t})

$\Gamma(Thr_t)$

Marcos Villagra

Je suppose qu'ils veulent éviter la fonction de valeur absolue. Ils obtiennent une forme plus facile de la fonction et évitent l'analyse au cas par cas pour tout calcul. Je suis intéressé par la façon dont ils obtiennent cette approximation de la fonction d'origine?

Marc Bury

C'est la même chose jusqu'à une constante.

Kristoffer Arnsfelt Hansen

Je ne sais pas comment obtenir ou voir la limite de partir de la limite d'origine mais voici la preuve que ces bornes sont asymptotiquement égales jusqu'à un facteur constant: $\sqrt{(t+1)(n-t+1)}$ $\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$

Voyons d'abord que (j'exclue car la fonction de seuil est toujours ) $t = 0$ $1$

n (n - | (2 (t - 1) - n + 1 |) = {\begin{cases} n (2 t - 1) & 1 \leq t \leq n / 2 + 1 / 2 \\ n (2 n - 2 t + 1) & n / 2 + 1 / 2 \leq t \leq n - 1 \end{cases}

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

Définissez , et . $f_1(t) = n(2t-1)$ $f_2(t) = n(2n-2t+1)$ $g(t) = (t+1)(n-t+1)$

Maintenant, vous devez calculer la valeur maximale (en fonction de dans les intervalles définis) des fractions , , et . Vous pouvez le faire avec un calcul différentiel ou une approximation à l'aide du graphique (avec assez grand): $t$ $f_1(t)/g(t)$ $f_2(t)/g(t)$ $g(t)/f_1(t)$ $g(t)/f_2(t)$ $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$

Cela vous donne et aussi le résultat souhaité

n (n - | 2 (t - 1) - n - 1 |) = Θ ((t + 1) (n - t + 1))

$n(n-\vert 2(t-1)-n-1\vert) = \Theta((t+1)(n-t+1))$

\sqrt{n (n - | 2 (t - 1) - n - 1 |)} = Θ (\sqrt{(t + 1) (n - t + 1)}) .

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

Existe-t-il un moyen plus simple de voir / d'obtenir ce résultat?

Marc Bury
la source

Oui, je pense que vous avez raison. Mon impression est que les auteurs originaux connaissaient cette borne inférieure en raison de certains résultats comme la coutume quantique. En calcul quantique, nous avons une limite supérieure de , et en appliquant le théorème de Paturi et les limites de l'adversaire, ils ont montré ce que vous venez de montrer ici.

\sqrt{(t + 1) (n - t + 1)}

$\sqrt{(t+1)(n-t+1)}$

Marcos Villagra

Merci pour vos efforts!! Je pense que c'est la réponse. Je suis plus convaincu maintenant que c'est peut-être le seul moyen d'obtenir ce résultat.

Marcos Villagra

Limites inférieures de la fonction de seuil

Réponses: