City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Нижняя оценка для монотонных схем, окончание
Boolean Functions Complexity

What: Lecture
When: Saturday, 01 November 2014, 19:00–20:30
Where: ПОМИ РАН

Description

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

Video