Что: | Лекция |
Когда: | Воскресенье, 26 октября 2014, 11:15–12:50 |
Где: | ПОМИ РАН |
Начало доказательства нижней оценки \(\Omega(\log^2 n)\) глубины монотонных формул для задачи достижимости в ориентированном графе. Сведение к коммуникационной сложности.