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

Первые оценки на формульную сложность.
Boolean Functions Complexity

What: Seminar
When: Wednesday, 22 February 2017, 18:30–19:50
Where: ПОМИ РАН

Description

В первой части доклада будут рассмотрены оценки, связывающие глубину и размер формул с гейтами входной степени 2 и с гейтами произвольной входной степени. Во второй части будет доказана квадратичная нижняя оценка на размер формул с гейтами входной степени 2.