Conjecture de sensibilité bloc de sensibilité - Implications

12

Soit une fonction booléenne de sensibilité s ( f ) et de sensibilité de bloc b s ( f ) .fs(f)bs(f)

La conjecture de conjecture de sensibilité Sensibilité-Bloc indique qu'il y a un tel que f , b s ( f ) s ( f ) c .c>0f, bs(f)s(f)c

Quelles sont les implications de la vérité et du mensonge de cette conjecture?

Veuillez également citer des références.

T ....
la source
2
Veuillez envisager de rendre la question et sa réponse plus utiles en fournissant des définitions des termes sensibilité et sensibilité de bloc.
Jan Johannsen
3
La conjecture de sensibilité a maintenant été prouvée par Hao Huang: arxiv.org/abs/1907.00847 .
Yuval Filmus
La conjecture de sensibilité @YuvalFilmus suit en conséquence. Alors peut-être que plus de conséquences tiennent.
T ....
c4

Réponses:

13

Voici ce que Scott Aaronson a à dire à ce sujet:

fffff

La vérification d'autres documents pertinents n'offre pas d'autres implications convaincantes:

  • Nisan et Szegedy décrivent la question mais n'offrent aucune motivation du tout.
  • Kenyon et Kutin mentionnent qu'il s'agit d'une «question ouverte naturelle».
  • Gotsman et Linial donnent un problème équivalent quelque peu artificiel (Conjecture 5.33 à la page 18 de l'article suivant).
  • P. Hatami, Kulkarni et Pankratov , dans leur enquête complète sur le problème, n'offrent également aucune motivation, mais ils ont plusieurs formulations équivalentes. Par exemple, la conjecture de sensibilité équivaut à la conjecture selon laquelle la complexité de décision de parité d'une fonction est polynomiale délimitée par la sensibilité. La conjecture 5.31 à la page 17, due à Shi, est une reformulation qui ne mentionne pas du tout la sensibilité.
  • Ambainis, Bavarian, Gao, Mao, Sun et Zao affirment que la conjecture "provient de la théorie des mesures de complexité des fonctions booléennes et de la complexité de l'arbre de décision", et offre généralement le même type de motivation que Scott Aaronson. Leur récente préimpression est le dernier mot de la conjecture (en décembre 2014).
Yuval Filmus
la source
5

Ω(log(s(f)))fCREW(f)f

CREW(f)=Ω(logs(f))

CREW(f)

CREW(f)=Θ(logbs(f))

CREW(f)=O(logs(f))

CREW(f)

Denis Pankratov
la source