Что: | Лекция |
Когда: | Суббота, 01 ноября 2014, 19:00–20:30 |
Где: | ПОМИ РАН |
Завершение доказательства нижней оценки $ 2^{\Omega(n^{\epsilon})} $ размера монотонных схем для функции «Клика»: монотонные схемы маленького размера приближаются дизъюнкцией малого числа индикаторных функций.