Пятница, 3 ноября, комната 106. Начало в 16:00.
Докладчик: А. С. Куликов.
Тема: Нижние оценки для булевы схем из -гейтов.
Доклад по статье Chattopadhyay, Goyal, Pudlak, Therien ``Lower bounds for circuits with gates''. Будет показано, что схема, состоящая только из -гейтов и вычисляющая функцию , требует хотя бы линейного количества гейтов.