Понедельник, 28 февраля, ауд. 203. Начало в 14:00.
Докладчик: А.С. Куликов (ПОМИ).
Тема: Вычисление всех MOD-функций одновременно.
Abstract
Для заданных констант $m$ и $r$, симметрическая булева функция
$\textrm{MOD}_{m,r} \colon \{0,1\}^n \rightarrow \{0,1\}$ определяется
следующим образом:
$\text{MOD}_{m,r}(x_1, \dots, x_n)=1 \Leftrightarrow \sum_{i=1}^n x_i
\equiv r \pmod{m} \, .$
Хорошо известно, что любая такая функция может быть вычислена схемами
размера $O(n)$. Мы рассмотрим ситуацию, когда необходимо вычислить
семейство функций
$\{ \text{MOD}_{1,r_1}, \text{MOD}_{2,r_2}, \dots, \text{MOD}_{n,r_n} \} \, .$
Будет показано, что если все $r_i$ равны, то для вычисления данного семейства
функций по-прежнему достаточно схем линейного размера. Вопрос же об
асимптотике минимального размера схем при произвольных $r_i$
остаётся открытым.
Доклад основан на результатах, полученных совместно с Е. Деменковым,
И. Михайлиным и Х. Морицуми.
