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

Линейные нижние оценки на схемы без ограничений и метод элиминации гейтов (А. Куликов)
Boolean Functions Complexity

What: Lecture
When: Sunday, 02 October 2011, 11:15–12:50
Where: ПОМИ РАН
Slides: boolean_functions_complexity_lecture_021011.pdf

Description

Основная идея метода элиминации гейтов. Примеры свойств функций, использующихся в доказательстве верхних оценок: \( 2n \) для функций, имеющих хотя бы три различные подфункции относительно любых двух переменных; \( 2n \) для функции индексации; \( 7n/3 \) для функций высокой степени.

Attached files