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

Монотонные формулы для задачи «Достижимость», нижняя оценка
Boolean Functions Complexity

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

Description

Завершение доказательства нижней оценки \(\Omega(\log^2 n)\) глубины монотонных формул для задачи достижимости в ориентированном графе. Оценка коммуникационной сложности.

Video