Семинар лаборатории теоретической информатики: "Нижние оценки тестирования двудольности с помощью коммуникационной сложности". Докладчик: А. Стороженко

27 февраля на семинаре лаборатории теоретической информатики
состоится доклад Андрея Стороженко "Нижние оценки тестирования двудольности с помощью коммуникационной сложности"

В докладе рассматриваются нижние оценки для тестирования двудольности. 
Предполагается, что алгоритм получает граф в виде оракула и может посылать запросы о ребрах и вершинах. Мы используем подход Eden и Rosenbaum (2018), при котором нижние оценки получаются с помощью сведения сложных задач коммуникационной сложности к задачам на графах. 
Будут обсуждаться сравнения различных моделей графов и нижняя оценка $\Omega(1/\epsilon)$ тестирования двудольности плотных графов. Также мы обсудим связь коммуникационной сложности и разрешающих деревьев в рамках используемых сведений.

Семинар пройдет с 18:10 до 19:30 в аудитории 503 ФКН.
Заказ пропуска: Чернышова Дина dchernyshova@hse.ru