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

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

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

Описание

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

Видео