Лаборатория алгоритмических методов

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

Дата:

Monday, September 29, 2014 - 18:00

Аннотация:

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