Схемы ограниченной глубины (Р. Колганов)
Сложность булевых функций


Что: Лекция
Когда: Воскресенье, 11 декабря 2011, 15:35–17:10
Где:
Слайды: boolean_functions_complexity_lecture_111211.pdf

Описание

Два способа доказательства нижних оценок на размеры схем ограниченной глубины: сокращение глубины с помощью леммы о переключении (Hastad's Switching Lemma) и аппроксимация схем полиномами маленькой степени. Примеры применения этих методов для схем, состоящих из чередующихся уровней AND и OR гейтов: получение с их помощью суперполиномиальной оценки на размеры таких схем, вычисляющих функции четности и голосования.

Материалы

Приложенные файлы