Пятница, 2 декабря, ауд. 106. Начало в 18:00.
Докладчик: Илья Разенштейн (МГУ).
Тема: Общая информация случайной пары строк.
Abstract
В докладе будет изучаться общая информация пары строк, которые сгенерированы по некоторому распределению. Рассмотрим такой модельный пример. Генерируются две случайные двоичные строки
длины
, расстояние Хемминга между которыми равно
. Мы хотим закодировать
в тройку строк
так, чтобы
восстанавливался по
, а
- по
. Очевидно, что должно выполняться неравенство
, чтобы
в принципе можно было восстановить по
. Мы усилим это неравенство до
. Это утверждение легко следует из количественной версии теоремы Гача-Кернера, которую мы докажем. В доказательстве используется оценка на норму оператора шума, который действует на произведении вероятностных пространств.