Límite superior en el grado de una función booleana en términos de su sensibilidad

Un problema abierto muy interesante en el estudio de las medidas de complejidad de la función booleana es la llamada conjetura de sensibilidad frente a sensibilidad de bloque. Para obtener información sobre la sensibilidad frente a la sensibilidad de bloque, puede consultar la siguiente publicación de blog de S. Aaronson en http://www.scottaaronson.com/blog/?p=453 .

Hasta donde sé, el mejor límite superior conocido en en términos de es $bs(f)$ $s(f)$ . [Documento de Kenyon, Kutin] Pero, por supuesto, quizás sea más conveniente relacionarcon alguna otra medida de complejidad desay, el grado decomo polinomio sobre, es decir, el tamaño de su coeficiente de Fourier más alto . $bs(f)=O(e^{s(f)}\sqrt{s(f)})$ $s(f)$ $f$ $\deg(f)$ $f$ $\mathbb{R}$

La pregunta es ¿cuál es el mejor límite superior conocido en en términos de ? $\deg(f)$ $s(f)$

cc.complexity-theory reference-request fourier-analysis Mohammad Bavarian
fuente

Puede usar el resultado de Nisan-Szegedy de que la complejidad del árbol de decisión determinista es

y tendrá

. Sin embargo, no sé si esto es mejor.

D (f) \leq b s^{4} (f)

$D(f)\leq bs^4(f)$

\tilde{d e g} (f) = O (e^{4 s (f)} s^{2} (f))

$\widetilde{deg}(f)=O(e^{4s(f)} s^2(f))$

Marcos Villagra

Estoy bastante seguro de que a nadie le ha ido mejor que a través de la conexión que Marcos menciona. Es más natural relacionar s con bs. deg (f) está polinómicamente relacionado con la mayoría de las otras cantidades, por ejemplo, D (f), bs (f), C (f), aprox-deg (f), etc. Puede disfrutar de la encuesta de Buhrman-De Wolf sobre la complejidad del árbol de decisión que revisa estas medidas.

Andy Drucker

d e g (f) \leq D T (f) \leq 4^{s (f)} \cdot p o l y (s (f))

$deg(f) \le DT(f) \le 4^{s(f)}\cdot poly(s(f))$

Límite superior en el grado de una función booleana en términos de su sensibilidad

Respuestas: