City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

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

What: Lecture
When: Sunday, 01 April 2012, 11:15–12:50
Where: ПОМИ РАН

Description

Теорема Зяблова и Пинскера о существование линейного кода размерности \( 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 \).

Video