Семинар лаборатории теоретической информатики: "Верхняя оценка на взаимную информацию через ранг матрицы совместного распределения". Докладчик: А. Рязанов
На очередном семинаре лаборатории теоретической информатики в среду 26 апреля состоится доклад
Андрея Рязанова
"Верхняя оценка на взаимную информацию через ранг матрицы совместного распределенияЭ".
Время проведения:18:10 - 19:30
Адрес мероприятия: Кочновский проезд, д. 3, ауд. 505
Заказ пропуска: evavilova@hse.ru
Аннотация:
Взаимная информация даёт нижнюю оценку на неотрицательные и положительно полуопределённые ранги матриц, которые связаны с возможностью представления многогранника как сечения конусов неотрицательных ортантов или положительно полуопределенных матриц, соответственно. Для многогранников сложных задач в предположении P≠NP неотрицательные и положительно полуопределенные ранги не могут быть полиномиальными по размерности, но построить явные сверхполиномиальные нижние оценки для рангов удалось пока только для некоторых частных случаев.
В докладе будет доказано, что взаимная информация произвольных случайных величин с конечным носителем ограничена сверху логарифмом ранга матрицы совместного распределения этих величин. Тем самым мы покажем, что нижняя оценка на неотрицательный и положително определенный ранги через взаимную информацию не может быть сверхполиномиальной. Также будут рассмотрены другие оценки из статьи T. Lee, Z. Wei, R. de Wolf и для них доказаны аналогичные результаты.