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

Speaker: 
Дмитрий Соколов
Date: 
Monday, September 29, 2014 - 18:00
Place: 
ПОМИ, аудитория 106
Abstract: 

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