Понедельник 17.04. А.Е. Ромащенко (LIRMM): "О геометрических и комбинаторных интерпретациях условных информационных неравенств"

[PDMI seminars]

Семинар по дискретной математике

Тема: О геометрических и комбинаторных интерпретациях условных информационных неравенств
Место: 106
Время: 17.04.2017, 17:00
Докладчик: А.Е. Ромащенко (LIRMM)

Abstract:
Следуя Н.Пиппенжеру, можно сказать, что наиболее общие "законы теории информации" выражаются в терминах линейных неравенств для энтропии Шеннона. Классические неравенства для энтропии (монотонность, субаддитивность, субмодулярность) восходят к работе К.Шеннона 1948 г. Эти неравенства имеют ясный интуитивный смысл. Например, субаддитивность энтропии $H(X,Y) \le H(X)+H(Y)$ означает, что "количество информации", заключенное в паре случайных величин (X,Y), не превосходит суммы объемов информации в X и Y соответственно. Известны многочисленные применения информационных неравенств. Каждое линейное неравенство для энтропии можно эквивалентным образом переформулировать на многих разных языках: как утверждения о конечных группах, о колмогоровской сложности, о размерах проекций конечных множеств, и т.д.

Известны и более экзотические утверждения о шенноновской энтропии -- так называемые условные информационные неравенства (constraint information inequalities). Каждое такое неравенство выполнено при некотором ограничении на рассматриваемые случайные величины. Например, неравенство Инглетона для энтропий четверки случайных величин (A,B,C,D) выполняется при условии I(A:B) = I(A:B|C) = 0. Известно лишь несколько нетривиальных примеров условных информационных неравенств, и до недавнего времени они казались бессодержательными артефактами определения энтропии.

Мы покажем, что условные информационные неравенства могут иметь вполне содержательный смысл и интересные применения. Мы обсудим связь условных неравенств с теоремой Матуша (конус энтропийных точек не полиэдрален), с бикликовым покрытием графа (оценки Куликова--Юкны) и некоторыми оценками для раскраски графов (Верещагин--Касед).

[Dmitry M. Itsykson]

Внимание, семинар состоится сегодня (17 апреля) в 17-00, но не в 106 аудитории, а в Мраморном зале.

С уважением,

Ицыксон Дмитрий.

--
You received this message because you are subscribed to the Google Groups "DM seminar" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dm-seminar+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.