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

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

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

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

Abstract

Булева функция

называется знаковой функцией целочисленного многочлена

, если

для всех

. При этом многочлен

называется пороговым элементом для булевой функции

. Весом порогового элемента называется сумма модулей его коэффициентов.

В докладе будет исследоваться величина

-- минимальный вес порогового элемента степени не выше

для булевой функции

. Будет представлена неулучшаемая нижняя оценка на

при постоянном

: для всех

и

существует булева функция от

переменных, реализуемая пороговым элементом степени

, и такая что

. Будет представлена однородная по степени нижняя оценка на

: для всех

и

существует функция от

переменных, реализуемая пороговым элементом степени

, для которой не только

велико, но и

велико, для

. Также будут обсуждаться другие вопросы связанные с изменением величины

при изменении

.