Схемы со средней входящей степенью
Докладчик:
Дмитрий Соколов
Дата:
Monday, September 29, 2014 - 18:00
Место:
ПОМИ, аудитория 106
Аннотация:
В докладе мы рассмотрим булевы схемы, в которых входная степень гейта ограничена линейной функцией от числа переменных. Мы докажем оценку \Omega(log^2 n) на явную функцию для подобных схем. Будет продемонстрирован метод применения коммуникационной сложности для доказательства нижних оценок на размер схем.
Доклад по статье: