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


Что: Лекция
Когда: Воскресенье, 26 октября 2014, 11:15–12:50
Где:

Описание

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

Видео