Монотонные формулы для задачи «Достижимость», нижняя оценка
Сложность булевых функций


Что: Лекция
Когда: Воскресенье, 26 октября 2014, 13:00–14:35
Где: ПОМИ РАН

Описание

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

Видео