Home

Понедельник 28-го февраля, 14-00

Понедельник, 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 $ остаётся открытым. Доклад основан на результатах, полученных совместно с Е. Деменковым, И. Михайлиным и Х. Морицуми.