Laboratory of Mathematical Logic at PDMI

Понедельник, 19 октября, комната 203. Начало в 12:00.

Докладчик: Владимир Подольский (Москва).

Тема: Оценки коэффициентов целочисленных многочленов с заданной знаковой булевой функцией.

Abstract

Булева функция $ f \colon \{-1,1\}^n \to \{-1,1\} $ называется знаковой функцией целочисленного многочлена $ p(x) $, если $ f(x) = \sgn p(x) $ для всех $ x \in \{-1,1\}^n $. При этом многочлен $ p(x) $ называется пороговым элементом для булевой функции $ f $. Весом порогового элемента называется сумма модулей его коэффициентов.

В докладе будет исследоваться величина $ W(f,d) $ -- минимальный вес порогового элемента степени не выше $ d $ для булевой функции $ f $. Будет представлена неулучшаемая нижняя оценка на $ W(f,d) $ при постоянном $ d $: для всех $ d $ и $ n $ существует булева функция от $ n $ переменных, реализуемая пороговым элементом степени $ d $, и такая что $ W(f,d) = n^{\Omega(n^d)} $. Будет представлена однородная по степени нижняя оценка на $ W(f,d) $: для всех $ n $ и $ d $ существует функция от $ n $ переменных, реализуемая пороговым элементом степени $ d $, для которой не только $ W(f,d) $ велико, но и $ W(f,D) $ велико, для $ D>d $. Также будут обсуждаться другие вопросы связанные с изменением величины $ W(f,d) $ при изменении $ d $.