Понедельник, 19 октября, комната 203. Начало в 12:00.
Докладчик: Владимир Подольский (Москва).
Тема: Оценки коэффициентов целочисленных многочленов с заданной знаковой булевой функцией.
Булева функция называется знаковой функцией целочисленного многочлена
, если
для всех
. При этом многочлен
называется пороговым элементом для булевой функции
. Весом порогового элемента называется сумма модулей его коэффициентов.
В докладе будет исследоваться величина -- минимальный вес порогового элемента степени не выше
для булевой функции
. Будет представлена неулучшаемая нижняя оценка на
при постоянном
: для всех
и
существует булева функция от
переменных, реализуемая пороговым элементом степени
, и такая что
. Будет представлена однородная по степени нижняя оценка на
: для всех
и
существует функция от
переменных, реализуемая пороговым элементом степени
, для которой не только
велико, но и
велико, для
. Также будут обсуждаться другие вопросы связанные с изменением величины
при изменении
.