Conjectura de sensibilidade de bloco de sensibilidade - implicações

Seja uma função booleana com sensibilidade s ( f ) e bloqueie a sensibilidade b s ( f ) .$f$$s(f)$$bs(f)$

A conjectura de conjectura de sensibilidade de bloco de sensibilidade afirma que existe um tal que ∀ f , b s ( f ) ≤ s ( f ) c .$c>0$$\forall f,\mbox{ }bs(f)\leq s(f)^c$

Quais são as implicações da verdade e da falsidade dessa conjectura?

Por favor, cite as referências também.

Aqui está o que Scott Aaronson tem a dizer sobre o assunto:

$f$$f$$f$$f$$f$

Verificar outra literatura relevante não oferece outras implicações convincentes:

• Nisan e Szegedy descrevem a pergunta, mas não oferecem nenhuma motivação.
• Kenyon e Kutin mencionam que essa é uma "questão natural aberta".
• Gotsman e Linial apresentam um problema equivalente, um tanto artificial (Conjectura 5.33 na página 18 do artigo a seguir).
• P. Hatami, Kulkarni e Pankratov , em sua pesquisa abrangente sobre o problema, também não oferecem motivação, mas eles têm várias formulações equivalentes. Por exemplo, a conjectura de sensibilidade é equivalente à conjectura de que a complexidade da decisão de paridade de uma função é polinomialmente limitada pela sensibilidade. A conjectura 5.31 na página 17, devido a Shi, é uma reformulação que não menciona sensibilidade.
• Ambainis, Bavarian, Gao, Mao, Sun e Zao afirmam que a conjectura "se origina da teoria da complexidade das medidas das funções booleanas e da complexidade da árvore de decisão" e geralmente oferece o mesmo tipo de motivação que Scott Aaronson. A recente pré-impressão é a última palavra da conjectura (em dezembro de 2014).

$\Omega( \log(s(f)) )$$f$$CREW(f)$$f$

$CREW(f) = \Omega(\log s(f))$

$CREW(f)$

$CREW(f) = \Theta(\log bs(f))$

$CREW(f) = O(\log s(f))$

$CREW(f)$