Limite superior no grau de uma função booleana em termos de sua sensibilidade

Um problema em aberto muito interessante no estudo de medidas de complexidade da função booleana é a chamada conjectura de sensibilidade versus sensibilidade de bloco. Para obter informações detalhadas sobre sensibilidade versus sensibilidade de bloco, consulte o seguinte post do blog de S. Aaronson em http://www.scottaaronson.com/blog/?p=453 .

Que eu saiba, o melhor limite superior conhecido em em termos de é $bs(f)$ $s(f)$ . [Kenyon, artigo de Kutin] Mas é claro que talvez seja mais conveniente relacionara alguma outra medida de complexidade desay, o grau decomo polinomial sobre, ou seja, o tamanho de seu coeficiente de Fourier mais alto . $bs(f)=O(e^{s(f)}\sqrt{s(f)})$ $s(f)$ $f$ $\deg(f)$ $f$ $\mathbb{R}$

A questão é qual é o melhor limite superior conhecido em em termos de ? $\deg(f)$ $s(f)$

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

Você pode usar o resultado de Nisan-Szegedy de que a complexidade da árvore de decisão determinística é

e você terá

. Não sei se é melhor assim.

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

Estou bastante confiante de que ninguém se saiu melhor do que através da conexão que Marcos menciona. É mais natural relacionar s com bs. deg (f) está polinomialmente relacionado à maioria das outras quantidades, por exemplo, D (f), bs (f), C (f), aprox-deg (f), etc. Você pode apreciar a pesquisa de Buhrman-De Wolf sobre a complexidade da árvore de decisão que analisa essas 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))$

Limite superior no grau de uma função booleana em termos de sua sensibilidade

Respostas: