Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 3 ноября, комната 106. Начало в 16:00.

Докладчик: А. С. Куликов.

Тема: Нижние оценки для булевы схем из $MOD_m$-гейтов.

Abstract

Доклад по статье Chattopadhyay, Goyal, Pudlak, Therien ``Lower bounds for circuits with $MOD_m$ gates''. Будет показано, что схема, состоящая только из $MOD_m$-гейтов и вычисляющая функцию $MOD_q$, требует хотя бы линейного количества гейтов.