Limite supérieure du degré d'une fonction booléenne en termes de sensibilité

Un problème ouvert très intéressant dans l'étude des mesures de complexité de la fonction booléenne est la conjecture dite de sensibilité vs sensibilité de bloc. Pour plus d'informations sur la sensibilité par rapport à la sensibilité aux blocs, vous pouvez consulter le blog suivant de S. Aaronson à http://www.scottaaronson.com/blog/?p=453 .

À ma connaissance, la meilleure borne supérieure connue sur en termes de est $bs(f)$ $s(f)$ . [Kenyon, Kutin paper] Mais bien sûr, il est peut-être plus commode de relierà une autre mesure de complexité dedisons, le degré decomme polynôme sur, c'est-à-dire la taille de son coefficient de Fourier le plus élevé . $bs(f)=O(e^{s(f)}\sqrt{s(f)})$ $s(f)$ $f$ $\deg(f)$ $f$ $\mathbb{R}$

La question est quelle est la meilleure borne supérieure connue sur en termes de ? $\deg(f)$ $s(f)$

cc.complexity-theory reference-request fourier-analysis Mohammad Bavarian
la source

Vous pouvez utiliser le résultat de Nisan-Szegedy selon lequel la complexité de l'arbre de décision déterministe est

et vous aurez

. Je ne sais pas si c'est le meilleur.

D (f) \leq b s^{4} (f)

$D(f)\leq bs^4(f)$

\tilde{d e g} (f) = O (e^{4 s (f)} s^{2} (f))

$\widetilde{deg}(f)=O(e^{4s(f)} s^2(f))$

Marcos Villagra

Je suis assez confiant que personne n'a fait mieux que via la connexion mentionnée par Marcos. Il est plus naturel de relier s à bs. deg (f) est polynomialement lié à la plupart des autres quantités, par exemple D (f), bs (f), C (f), approx-deg (f), etc. Vous pouvez apprécier l'enquête Buhrman-De Wolf sur la complexité de l'arbre de décision qui examine ces mesures.

Andy Drucker

Je pense que la preuve de Simon des années 80 donne une limite légèrement meilleure: quelque chose comme

d e g (f) \leq D T (f) \leq 4^{s (f)} \cdot p o l y (s (f))

$deg(f) \le DT(f) \le 4^{s(f)}\cdot poly(s(f))$

Avishay Tal

Limite supérieure du degré d'une fonction booléenne en termes de sensibilité

Réponses: