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