Na conjectura de sensibilidade?

8

O recente estabelecimento da relação bs(f)=O(s(f)4) passa por Gotsman, Linial .

A mesma abordagem pode chegar a O(s(f)2) ou existe uma limitação essencial à abordagem?

T ....
fonte
1
Isso é discutido nas observações finais do artigo de Hao Huang (sob o terceiro item). Huang escreve: "Talvez alguém possa fechar essa lacuna aplicando diretamente o método espectral a funções booleanas, em vez de hipercubos".
31419 Gamow

Respostas:

17

(1)f:{0,1}n{0,1},s(f)degf
(2)f:{0,1}n{0,1},degf12bsf
bsf(degf)log36
log361.63

Por outro lado, é possível que o uso de técnicas semelhantes (ou seja, entrelaçamento de autovalores de matrizes assinadas), mas em objetos diferentes (em primeiro lugar, sem usar o grau como proxy) possa levar a limites mais nítidos. Isso é explicitamente declarado como questão em aberto no artigo de Huang [4]:

Talvez alguém possa fechar essa lacuna [quadrática versus quártica] aplicando diretamente o método espectral a funções booleanas, em vez de hipercubos.


[1] Noam Nisan e Mario Szegedy. No grau de funções booleanas como polinômios reais . Comput. Complexity, 4: 462–467, 1992. doi: 10.1007 / BF01263419

[2] Pooya Hatami, Raghav Kulkarni e Denis Pankratov, variações na conjectura de sensibilidade. Pesquisa de pós-graduação em teoria da computação, 2011. https://theoryofcomputing.org/articles/gs004/

[3] Noam Nisan e Avi Wigderson. Na classificação versus complexidade da comunicação . Combinatorica, 15: 557-565, 1995. doi: 10.1007 / BF01192527

[4] Hao Huang. Subgráficos induzidos de hipercubos e uma prova da conjectura de sensibilidade. arXiv: 1907.00847, 2019. https://arxiv.org/abs/1907.00847

Clemente C.
fonte