¿Sobre la conjetura de la sensibilidad?

Del documento: lo que realmente está probado es, en el Teorema 1.4, que no se puede mejorar (es limitado para algunas funciones). Luego se combina con el resultado previamente conocido de Nisan y Szegedy [1], (una separación, por cierto, preguntaste hace unos años ). De esta encuesta [2] (ver Tabla 1), la referencia [3], (2) no puede mejorarse más allá de donde . Por lo tanto, esta vía de usar el grado como proxy no puede

\begin{matrix} (1) & \forall f : {0, 1}^{n} \to {0, 1}, s (f) \geq \sqrt{\deg f} \end{matrix}

$\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad s(f) \geq \sqrt{\deg f} \tag{1}$

\begin{matrix} (2) & \forall f : {0, 1}^{n} \to {0, 1}, \deg f \geq \sqrt{\frac{1}{2} bs f} \end{matrix}

$\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad \deg f \geq \sqrt{\frac{1}{2}\operatorname{bs} f} \tag{2}$

bs f ≳ (\deg f)^{\log_{3} 6}

$\operatorname{bs} f \gtrsim (\deg f)^{\log_3 6}$

\log_{3} 6 \approx 1.63

$\log_3 6 \approx 1.63$ dar un límite superior de sensibilidad cuadrática en la sensibilidad del bloque.

Por otro lado, es posible que el uso de técnicas similares (es decir, entrelazar valores propios de matrices con signo) pero en diferentes objetos (en primer lugar, sin usar el grado como proxy) pueda conducir a límites más agudos. Esto se afirma explícitamente como una pregunta abierta en el artículo de Huang [4]:

Quizás uno podría cerrar esta brecha [cuadrática vs. cuártica] aplicando directamente el método espectral a las funciones booleanas en lugar de a los hipercubos.

[1] Noam Nisan y Mario Szegedy. Sobre el grado de funciones booleanas como polinomios reales . Comput Complejidad, 4: 462–467, 1992. doi: 10.1007 / BF01263419

[2] Pooya Hatami, Raghav Kulkarni y Denis Pankratov, Variaciones sobre la conjetura de la sensibilidad. Teoría de la Computación Encuesta de Posgrado, 2011. https://theoryofcomputing.org/articles/gs004/

[3] Noam Nisan y Avi Wigderson. En rango vs. complejidad de comunicación . Combinatorica, 15: 557–565, 1995. doi: 10.1007 / BF01192527

[4] Hao Huang. Subgrafías inducidas de hipercubos y una prueba de la Conjetura de la sensibilidad. arXiv: 1907.00847, 2019. https://arxiv.org/abs/1907.00847

Clemente C.
fuente

¿Sobre la conjetura de la sensibilidad?

Respuestas: