Abstract:
В докладе рассматривается соотношение между двумя мерами сложности булевых функций: степенью многочлена $d(f)$, выражающего функцию над полем вещественных чисел, и блочной чувствительностью $bs(f)$. Мы улучшаем текущую оценку $ d^2(f) \geq bs(f) $, установленную Талом, до $ d^2(f) \geq (\sqrt{10} - 2)bs(f) $. Как следствие, мы также улучшаем оценки для некоторых других пар мер сложности. Например, мы улучшаем мультипликативную константу в недавнем результате из доказательства гипотезы чувствительности.
В следующем результате мы получаем похожее продвижение для разрыва между блочной чувствительностью и степенью приближающего многочлена $\deg_{1/3}^2(f)$: мы доказываем, что $\deg_{1/3}^2(f) \geq \sqrt{6/101} bs(f)$ и тем самым улучшаем предыдущую оценку $ \deg_{1/3}(f) \geq \sqrt{bs(f)/6} $, доказанную Нисаном и Сегери. В дополнение мы также строим пример, который показывает, что разница между константами в нижних и верхних оценках на степень не превосходит $0.2$.
В последнем результате мы изучаем свойства гипотетической полностью чувствительной в нуле функции от 10 переменных степени 4. Существование такой функции усилило бы разрыв между чувствительностью и степенью булевой функции. Мы доказываем, что в результате симметризации такой функции может получиться единственный многочлен, и явно приводим его формулу.
