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