Каковы применения кодов, исправляющих ошибки в теории, помимо самого исправления ошибок? Мне известны три приложения: теорема Голдрайха-Левина о жестком ядре, конструкция экстрактора Тревизана и усиление твердости булевой функции (Судан-Тревизан-Вадхан).
Каковы другие «серьезные» или «развлекательные» применения кодов, исправляющих ошибки?
UPD: одно забавное приложение списочного декодирования кодов Рида-Соломона - это решение для конкретного варианта игры из 20 вопросов (и другое , более простое, изменение).
Ответы:
Вот прямое приложение в сложности коммуникации (которое я вижу сейчас, также описано в комментарии Энди Друкера в его блоге ) вне контекста дерандомизации:
Предположим , что Алиса и Боб приведены строки и соответственно, и они хотят , чтобы выяснить , если расстояние Хэмминга между и не больше (где некоторая фиксированная константа). Мы хотим доказать нижнюю границу сложности связи для этой проблемы. Наблюдение состоит в том, что любой детерминированный протокол для этой задачи дает детерминированный протокол с тем же числом раундов для проверки равенства двух строк и длины где - некоторая константа, зависящая от . Зачем? Для проверки равенстваy x y ϵ n ϵ a b c n c < 1 ϵ aИкс Y Икс Y ϵ н ε a б с п с < 1 ε a и Алиса и Боб могут запустить протокол для первой проблемы на и где - это код с исправлением ошибок с расстоянием не менее . Поскольку существует легкая линейная нижняя оценка для проблемы равенства, это также дает детерминистическую линейную нижнюю оценку для первой задачи.C ( a ) C ( b ) C ϵб С( а ) С( б ) С ε
источник
Существует огромное количество приложений кодов с исправлением ошибок в теоретической информатике.
Классическое применение [которое, я думаю, не было упомянуто выше] - это создание экстракторов / сэмплеров случайности; см., например, здесь: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm
Есть также много приложений для криптографии, и я уверен, что один из информированных читателей был бы рад разработать :)
источник
Вот новое приложение, горячее от прессов! В новом отчете ECCC Ор Меира это выглядит следующим образом:
источник
Существует ряд работ по стеганографии и скрытым вычислениям (начинающихся здесь ), которые в основном требуют кодов, исправляющих ошибки. Они моделируют неудачные вызовы оракула, чтобы извлечь из произвольного распределения шум в канале.
источник
Несколько других примеров:
Возведениеε ε
Улучшенное быстрое рандомизированное уменьшение размерности (Быстрое преобразование Джонсона-Линденштраусса), в Ailon-Liberty, SODA'08 .
источник
Коды исправления ошибок используются в криптографии для решения проблемы согласования информации : Алиса и Боб хотят согласовать ключ K, начиная с (коррелированных) строк X и Y, соответственно. (Примером такой ситуации является протокол, который основан на шумном канале, когда Алиса отправляет X Бобу.) Решение состоит в том, чтобы заставить Алису посылать Бобу некоторую информацию для исправления ошибок C Бобу, чтобы он мог восстановить X. Конечно, проблема в том, что не все так просто: поскольку C передает некоторую информацию злоумышленнику Еве, нам необходимо усилить конфиденциальность, чтобы получить секретный ключ. Это можно сделать с помощью 2-универсальной хеш-функции, что гарантируется оставшейся хеш-леммой.
Совсем недавно, в качестве помехоустойчивого варианта экстракторов были введены нечеткие экстракторы : они извлекают равномерно случайную строку R из своего ввода W, а также выдают «отпечаток» P, такой, что если на входе изменяется какая-то похожая строка W ', случайная строка R может быть восстановлен из P и W '. Конструкция нечетких экстракторов также опирается на коды с исправлением ошибок.
источник
Энди Друкер уже упоминал опрос Trevisan [Tre04] в комментарии к другому ответу , но я думаю, что его следует упомянуть более крупным шрифтом!
[Tre04] Лука Тревизан. Некоторые приложения теории кодирования в вычислительной сложности. Quaderni di Matematica , 13: 347–424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf
источник
Действительно, как упоминала Дана, есть много примеров.
В расчетах на отказоустойчивость коды с исправлением ошибок очень важны. Я думаю, что статья 1988 года Бен-Ор Гольдвассера и Вигдерсона Теоремы о полноте для не криптографических распределенных вычислений с отказоустойчивостью , хотя и без явного цитирования результатов кодов, исправляющих ошибки, имеет тип ECC.
Конечно, «пороговая теорема», допускающая отказоустойчивые квантовые вычисления, в решающей степени опирается на квантовые коды с исправлением ошибок, которые являются квантовыми аналогами обычных ECC.
( Статья в Википедии для пороговой теоремы, безусловно, нуждается в работе; но статья о квантовом исправлении ошибок лучше.)
источник
Ознакомьтесь со списком документов ECCC, помеченных «кодами, исправляющими ошибки» .
Изучив этот список, вы увидите, что существует связь между кодами, исправляющими ошибки, и PCP (я не знаю, будете ли вы считать это приложением «помимо простого исправления ошибок»), а также обучением PAC .
источник
Для очень хорошего объяснения того, как коды с исправлением ошибок используются в конкретной практической ситуации, посмотрите на:
Математика компакт-диска, Джек Х. Ван Линт, «Математика везде», М. Эйгнер и Э. Берендс (редакторы), Американское математическое общество, 2010
(Эта книга является переводом с немецкого оригинала.)
источник
Другое приложение в кодах аутентификации. По сути, это кодировки, предназначенные для обнаружения любых изменений в сообщении и основанные на исправлении ошибок. Это несколько больше, чем простое исправление ошибок, которое влечет за собой предположения о структуре шума.
источник
У кода с исправлением ошибок были приложения в тестировании свойств:
Тестирование функциональных свойств:
Тестирование распределения: аналог методологии нижней границы [BBM], упомянутой выше, также использует коды с исправлением ошибок в качестве ключевого компонента: тестирование распределения нижних границ с помощью сокращения от сложности связи , по Blais, Canonne и Gur.
(Извините, это немного смещено в сторону статей, которые я написал в соавторстве, в основном из-за моего знакомства с ними.)
источник
Мы считаем, что основанная на коде криптография с открытым ключом является постквантовой. На самом деле криптография на основе кода имеет самую длинную историю в истории постквантовых схем с открытыми ключами, но размеры ключей кажутся непрактично большими, как 1 МБ в McBits .
Мы также используем коды с исправлением ошибок в криптографии с открытым ключом на основе решетки, которая использует фазу согласования, как упоминал Фелипе Ласерда. На самом деле, наша лучшая ставка для постквантового обмена ключами - это схема модуля-LWE Кибера (на основе решетки).
источник