Понедельник, 28 февраля, ауд. 203. Начало в 14:00.
Докладчик: А.С. Куликов (ПОМИ).
Тема: Вычисление всех MOD-функций одновременно.
Abstract
Для заданных констант
![$ m $](../../../sites/default/files/tex/05b806fb3a39e75606f12e544fec1ae578c32b0b/index.png)
и
![$ r $](../../../sites/default/files/tex/487427599b496e67b56439e6a9bee69ad60b4095/index.png)
, симметрическая булева функция
![$ \textrm{MOD}_{m,r} \colon \{0,1\}^n \rightarrow \{0,1\} $](../../../sites/default/files/tex/9aafa424b819339527a22764ceef4a70f8775870/index.png)
определяется
следующим образом:
![$ \text{MOD}_{m,r}(x_1, \dots, x_n)=1 \Leftrightarrow \sum_{i=1}^n x_i
\equiv r \pmod{m} \, . $](../../../sites/default/files/tex/3bc8314987fed802f5587ca56bb677abb7169e63/index.png)
Хорошо известно, что любая такая функция может быть вычислена схемами
размера
![$ O(n) $](../../../sites/default/files/tex/eb0d619266e5bea34adf3cd93ec26bf7ba2330b0/index.png)
. Мы рассмотрим ситуацию, когда необходимо вычислить
семейство функций
![$ \{ \text{MOD}_{1,r_1}, \text{MOD}_{2,r_2}, \dots, \text{MOD}_{n,r_n} \} \, . $](../../../sites/default/files/tex/399ec1dbbb0362aacfad680b6b256a018eccff81/index.png)
Будет показано, что если все
![$ r_i $](../../../sites/default/files/tex/6f62a93ca4c06e137e6519b7f798688639f98bfa/index.png)
равны, то для вычисления данного семейства
функций по-прежнему достаточно схем линейного размера. Вопрос же об
асимптотике минимального размера схем при произвольных
![$ r_i $](../../../sites/default/files/tex/6f62a93ca4c06e137e6519b7f798688639f98bfa/index.png)
остаётся открытым.
Доклад основан на результатах, полученных совместно с Е. Деменковым,
И. Михайлиным и Х. Морицуми.