Верхний предел степени булевой функции с точки зрения ее чувствительности

Очень интересной открытой проблемой при изучении мер сложности булевой функции является так называемая гипотеза чувствительности и блочной чувствительности. Информацию о восприимчивости и чувствительности блоков вы можете найти в следующем посте С. Ааронсона по адресу http://www.scottaaronson.com/blog/?p=453 .

Насколько мне известно, лучшая верхняя граница, известная для в терминах равна $bs(f)$ $s(f)$ . [Кеньон, статья Кутина] Но, конечно, может быть, удобнее связатьс какой-то другой мерой сложностискажем,, степеньюкак многочлена над, то есть размером ее наибольшего коэффициента Фурье , $bs(f)=O(e^{s(f)}\sqrt{s(f)})$ $s(f)$ $f$ $\deg(f)$ $f$ $\mathbb{R}$

Вопрос в том, какова лучшая верхняя граница, известная для в терминах ? $\deg(f)$ $s(f)$

cc.complexity-theory reference-request fourier-analysis Мухаммед Баварский
источник

Вы можете использовать результат Нисана-Сегеди, согласно которому сложность дерева детерминированных решений составляет

и вы будете иметь

. Я не знаю, если это лучше, хотя.

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

Маркос Вильягра

Я вполне уверен, что никто не добился большего успеха, чем через связь, о которой упоминает Маркос. Наиболее естественно связать с бс. градус (f) полиномиально связан с большинством других величин, например, D (f), bs (f), C (f), приблизительный градус (f) и т. д. Вам может понравиться обзор Бюрмана-Вольфа о сложности дерева решений который рассматривает эти меры.

Энди Друкер

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

Верхний предел степени булевой функции с точки зрения ее чувствительности

Ответы: