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

11

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 s ( f ) é b s ( f ) = O ( e s ( f ) bs(f)s(f). [Kenyon, artigo de Kutin] Mas é claro que talvez seja mais conveniente relacionars(f)a alguma outra medida de complexidade defsaydeg(f), o grau defcomo polinomial sobreR, ou seja, o tamanho de seu coeficiente de Fourier mais alto .bs(f)=O(es(f)s(f))s(f)fdeg(f)fR

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

Mohammad Bavarian
fonte
3
Você pode usar o resultado de Nisan-Szegedy de que a complexidade da árvore de decisão determinística é e você terá ~ d e g ( f ) = O ( e 4 s ( f ) s 2 ( f ) ) . Não sei se é melhor assim. D(f)bs4(f)deg~(f)=O(e4s(f)s2(f))
Marcos Villagra
1
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
2
deg(f)DT(f)4s(f)poly(s(f))

Respostas:

9

bs(f)s(f)

bs(f)2s(f)1s(f).

Isso, juntamente com a conexão que Marcos mencionou em seu comentário, deveria dar melhores limites do que se sabia anteriormente.

Alessandro Cosentino
fonte