Семинар МЛ ТИ: "О разрыве между степенью булевой функции и блочной чувствительностью"

24 февраля, в среду, в 18:10 пройдет семинар лаборатории теоретической информатики.

Докладчик: Николай Проскурин

«О разрыве между степенью булевой функции и блочной чувствительностью»

В докладе рассматривается соотношение между двумя мерами сложности булевых функций: степенью многочлена $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. Существование такой функции усилило бы разрыв между чувствительностью и степенью булевой функции. Мы доказываем, что в результате симметризации такой функции может получиться единственный многочлен, и явно приводим его формулу.

Доклад пройдет в zoom, необходима регистрация по ссылке: https://zoom.us/meeting/register/tJArc--hrD8iHN3nh3noQ_8yn_dNnNMs_Amm