Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Нижняя оценка для монотонных схем, окончание
Сложность булевых функций

Что: Лекция
Когда: Суббота, 01 ноября 2014, 19:00–20:30
Где: ПОМИ РАН

Описание

Завершение доказательства нижней оценки \( 2^{\Omega(n^{\epsilon})} \) размера монотонных схем для функции «Клика»: монотонные схемы маленького размера приближаются дизъюнкцией малого числа индикаторных функций.

Видео