Conjetura de sensibilidad de bloqueo de sensibilidad - Implicaciones

12

Sea una función booleana con sensibilidad s ( f ) y sensibilidad de bloque b s ( f ) .fs(f)bs(f)

La conjetura de sensibilidad del bloque de sensibilidad establece que hay un tal que f , b s ( f ) s ( f ) c .c>0f, bs(f)s(f)c

¿Cuáles son las implicaciones de la verdad y la falsedad de esta conjetura?

Por favor, cita referencias también.

T ....
fuente
2
Considere hacer que la pregunta y su respuesta sean más útiles al proporcionar definiciones de los términos sensibilidad y sensibilidad de bloque.
Jan Johannsen
3
La conjetura de sensibilidad ahora ha sido probada por Hao Huang: arxiv.org/abs/1907.00847 .
Yuval Filmus
@YuvalFilmus La conjetura de sensibilidad se sigue como consecuencia. Entonces, tal vez se mantengan más consecuencias.
T ....
c4

Respuestas:

13

Esto es lo que Scott Aaronson tiene que decir sobre el tema:

fffff

Verificar otra literatura relevante no ofrece ninguna otra implicación convincente:

  • Nisan y Szegedy describen la pregunta pero no ofrecen ninguna motivación.
  • Kenyon y Kutin mencionan que es una "pregunta abierta natural".
  • Gotsman y Linial dan un problema equivalente algo artificial (Conjetura 5.33 en la página 18 del siguiente artículo).
  • P. Hatami, Kulkarni y Pankratov , en su exhaustiva encuesta sobre el problema, tampoco ofrecen motivación, pero tienen varias formulaciones equivalentes. Por ejemplo, la conjetura de sensibilidad es equivalente a la conjetura de que la complejidad de decisión de paridad de una función está polinómicamente limitada por la sensibilidad. La conjetura 5.31 en la página 17, debido a Shi, es una reformulación que no menciona la sensibilidad en absoluto.
  • Ambainis, Bavarian, Gao, Mao, Sun y Zao afirman que la conjetura "se origina en la teoría de las medidas de complejidad de las funciones booleanas y la complejidad del árbol de decisión", y en general ofrecen el mismo tipo de motivación que Scott Aaronson. Su preimpresión reciente es la última palabra sobre la conjetura (a diciembre de 2014).
Yuval Filmus
fuente
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
fuente