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

11

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 s ( f ) est b s ( f ) = O ( e s ( f ) bs(F)s(F). [Kenyon, Kutin paper] Mais bien sûr, il est peut-être plus commode de reliers(f)à une autre mesure de complexité defdisonsdeg(f), le degré defcomme polynôme surR, c'est-à-dire la taille de son coefficient de Fourier le plus élevé .bs(F)=O(es(F)s(F))s(F)Fdeg(F)FR

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

Mohammad Bavarian
la source
3
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 ~ d e g ( f ) = O ( e 4 s ( f ) s 2 ( f ) ) . Je ne sais pas si c'est le meilleur. (F)bs4(F)eg~(F)=O(e4s(F)s2(F))
Marcos Villagra
1
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
2
Je pense que la preuve de Simon des années 80 donne une limite légèrement meilleure: quelque chose comme . eg(F)T(F)4s(F)poly(s(F))
Avishay Tal

Réponses:

9

Ce document est venu sur l'arXiv aujourd'hui et il améliore la limite supérieure de en termes de s ( f ) . Ils prouvent la borne suivante:bs(F)s(F)

bs(F)2s(F)-1s(F).

Cela, ainsi que le lien que Marcos a mentionné dans son commentaire, devraient donner de meilleures limites que celles précédemment connues.

Alessandro Cosentino
la source