Схемы со средней входящей степенью

Докладчик: 
Дмитрий Соколов
Дата: 
Monday, September 29, 2014 - 18:00
Место: 
ПОМИ, аудитория 106
Аннотация: 

В докладе мы рассмотрим булевы схемы, в которых входная степень гейта ограничена линейной функцией от числа переменных. Мы докажем оценку \Omega(log^2 n) на явную функцию для подобных схем. Будет продемонстрирован метод применения коммуникационной сложности для доказательства нижних оценок на размер схем.