Górna granica stopnia funkcji boolowskiej pod względem jej czułości

Bardzo interesującym otwartym problemem w badaniu miar złożoności funkcji boolowskiej jest tak zwana hipoteza wrażliwości vs. blokowa. Informacje na temat wrażliwości kontra czułości bloków można znaleźć na następującym blogu S. Aaronsona na stronie http://www.scottaaronson.com/blog/?p=453 .

Według mojej najlepszej wiedzy, najlepszą górną granicą znaną na w kategoriach jest $bs(f)$ $s(f)$ . [Kenyon, papier Kutina] Ale oczywiście może wygodniej jest powiązaćz jakąś inną miarą złożonościpowiedzmy, stopniemjako wielomianem nad, tj. Rozmiarem jego najwyższego współczynnika Fouriera . $bs(f)=O(e^{s(f)}\sqrt{s(f)})$ $s(f)$ $f$ $\deg(f)$ $f$ $\mathbb{R}$

Pytanie brzmi: jaka jest najlepsza górna granica znana na pod względem ? $\deg(f)$ $s(f)$

cc.complexity-theory reference-request fourier-analysis Mohammad Bavarian
źródło

Możesz użyć wyniku Nisana-Szegedy, że złożoność deterministycznego drzewa decyzyjnego wynosi

i będziesz miał

. Nie wiem jednak, czy tak jest najlepiej.

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,

Jestem całkiem pewien, że nikt nie poradził sobie lepiej niż przez połączenie wspomniane przez Marcosa. Najbardziej naturalne jest odniesienie s do bs. deg (f) jest wielomianowo powiązany z większością innych wielkości, np. D (f), bs (f), C (f), ca. deg-f (f) itp. Możesz cieszyć się ankietą Buhrman-De Wolf dotyczącą złożoności drzewa decyzyjnego który dokonuje przeglądu tych środków.

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))$

Górna granica stopnia funkcji boolowskiej pod względem jej czułości

Odpowiedzi: