Home

Семинар 3 ноября 2006 года

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

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

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

Abstract

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