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

Схемы ограниченной глубины: приближение многочленами
Boolean Functions Complexity

What: Lecture
When: Sunday, 02 November 2014, 13:00–14:35
Where: ПОМИ РАН

Description

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

Video