• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Семинар лаборатории теоретической информатики: "Верхняя оценка на взаимную информацию через ранг матрицы совместного распределения". Докладчик: А. Рязанов

Мероприятие завершено

На очередном семинаре лаборатории теоретической информатики в среду 26 апреля состоится доклад 
Андрея Рязанова
"Верхняя оценка на взаимную информацию через ранг матрицы совместного распределенияЭ".
Время проведения:18:10 - 19:30
Адрес мероприятия: Кочновский проезд, д. 3, ауд. 505
Заказ пропуска: evavilova@hse.ru

 Аннотация:

Взаимная информация даёт нижнюю оценку на неотрицательные и положительно полуопределённые ранги матриц, которые связаны с возможностью представления многогранника как сечения конусов неотрицательных ортантов или положительно полуопределенных матриц, соответственно. Для многогранников сложных задач в предположении P≠NP неотрицательные и положительно полуопределенные ранги не могут быть полиномиальными по размерности, но построить явные сверхполиномиальные нижние оценки для рангов удалось пока только для некоторых частных случаев. 

В докладе будет доказано, что взаимная информация произвольных случайных величин с конечным носителем ограничена сверху логарифмом ранга матрицы совместного распределения этих величин. Тем самым мы покажем, что нижняя оценка на неотрицательный и положително определенный ранги через взаимную информацию не может быть сверхполиномиальной. Также будут рассмотрены другие оценки из статьи T. Lee, Z. Wei, R. de Wolf и для них доказаны аналогичные результаты.