Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

От декодирования списком и к однозначному декодированию
Теория кодирования


Что: Лекция
Когда: Воскресенье, 01 апреля 2012, 11:15–12:50
Где: ПОМИ РАН

Описание

Теорема Зяблова и Пинскера о существование линейного кода размерности \( k \) с кодовыми словами длины \( n \), допускающего декодирование списком размера \( O(1) \) на расстоянии \( e \) (достаточное условие \( V(n,e)<2^{(1-\varepsilon)(n-k)} \) для произвольного \( \varepsilon>0 \)). Коммуникационная задача передачи \( n \)-битного \( x \) от Алисы к Бобу при условии, что Бобу заранее известно некоторое \( y \) на расстоянии \( \alpha n \) от \( x \). Нижняя оценка коммуникационной сложности \( h(\alpha)n-o(n) \) (для \( \alpha<1/2 \)). Детерминированный 3-раундовый детерминированный коммуникационный протокол с коммуникационной сложностью \( h(\alpha)n+o(n) \) для \( \alpha<1/2 \).

Видео