Использование кодов, исправляющих ошибки в теории

39

Каковы применения кодов, исправляющих ошибки в теории, помимо самого исправления ошибок? Мне известны три приложения: теорема Голдрайха-Левина о жестком ядре, конструкция экстрактора Тревизана и усиление твердости булевой функции (Судан-Тревизан-Вадхан).

Каковы другие «серьезные» или «развлекательные» применения кодов, исправляющих ошибки?

UPD: одно забавное приложение списочного декодирования кодов Рида-Соломона - это решение для конкретного варианта игры из 20 вопросов (и другое , более простое, изменение).

ильяраз
источник
1
Может быть, я буду глупым, но никто не говорил о теореме PCP
AntonioFa

Ответы:

23

Вот прямое приложение в сложности коммуникации (которое я вижу сейчас, также описано в комментарии Энди Друкера в его блоге ) вне контекста дерандомизации:

Предположим , что Алиса и Боб приведены строки и соответственно, и они хотят , чтобы выяснить , если расстояние Хэмминга между и не больше (где некоторая фиксированная константа). Мы хотим доказать нижнюю границу сложности связи для этой проблемы. Наблюдение состоит в том, что любой детерминированный протокол для этой задачи дает детерминированный протокол с тем же числом раундов для проверки равенства двух строк и длины где - некоторая константа, зависящая от . Зачем? Для проверки равенстваy x y ϵ n ϵ a b c n c < 1 ϵ axyxyϵnϵabcnc<1ϵaи Алиса и Боб могут запустить протокол для первой проблемы на и где - это код с исправлением ошибок с расстоянием не менее . Поскольку существует легкая линейная нижняя оценка для проблемы равенства, это также дает детерминистическую линейную нижнюю оценку для первой задачи.C ( a ) C ( b ) C ϵbC(a)C(b)Cϵ

Арнаб
источник
Очень аккуратное приложение!
Ильяраз
1
Но ... Разве мы не можем просто дополнить достаточным количеством нулей, а - единицами? уxy
ильяраз
ilyaraz - если бы мы это сделали, то даже если x, y были бы равны start, у них было бы большое расстояние Хэмминга после заполнения. Смысл использования карты C () состоит в том, чтобы сохранить равенство и одновременно усилить неравенство.
Энди Друкер
Но мы хотим различить две ситуации: маленький вес Хэмминга и большой вес Хэмминга. Почему мы хотим заботиться о сохранении равенства?
Ильяраз
3
Самое интересное использование этой идеи - на самом деле доказать верхнюю границу рандомизированной коммуникационной сложности равенства: просто сравните случайный бит из C (a) и C (b). Если a = b, то вы обязательно получите равенство, в противном случае у вас есть вероятность получить неравенство. Это требует O (logn) битов (чтобы выбрать индекс сравниваемого бита), и если стороны имеют общую случайность, то сложность составляет всего O (1).
Noam
17

Существует огромное количество приложений кодов с исправлением ошибок в теоретической информатике.

Классическое применение [которое, я думаю, не было упомянуто выше] - это создание экстракторов / сэмплеров случайности; см., например, здесь: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm

Есть также много приложений для криптографии, и я уверен, что один из информированных читателей был бы рад разработать :)

Дана Мошковиц
источник
Я думаю, что ОП упомянул конструкцию экстрактора Тревизана в этом вопросе.
Суреш Венкат
14

Вот новое приложение, горячее от прессов! В новом отчете ECCC Ор Меира это выглядит следующим образом:

Теорема IP, которая утверждает, что IP = PSPACE (Lund et. Al. И Shamir, в J. ACM 39 (4)), является одним из главных достижений теории сложности. Известные доказательства теоремы основаны на методе арифметизации, которая преобразует количественную булеву формулу в связанный многочлен. Интуиция, лежащая в основе использования полиномов, обычно объясняется тем фактом, что полиномы представляют собой хорошие коды, исправляющие ошибки. Однако известные доказательства кажутся адаптированными к использованию полиномов и не обобщаются на произвольные коды с исправлением ошибок.

В этой работе мы покажем, что теорема IP может быть доказана с использованием общих кодов, исправляющих ошибки. Мы считаем, что это создает строгую основу для вышеупомянутой интуиции и проливает дополнительный свет на теорему ИС.

Суреш Венкат
источник
Я видел ваш комментарий, когда я собирался опубликовать тот же. Ницца!
Ильяраз
8

Существует ряд работ по стеганографии и скрытым вычислениям (начинающихся здесь ), которые в основном требуют кодов, исправляющих ошибки. Они моделируют неудачные вызовы оракула, чтобы извлечь из произвольного распределения шум в канале.

Даниэль Апон
источник
7

Несколько других примеров:

  • Возведение ϵϵ

  • Улучшенное быстрое рандомизированное уменьшение размерности (Быстрое преобразование Джонсона-Линденштраусса), в Ailon-Liberty, SODA'08 .

Петр
источник
Очень хороший ответ!
ильяраз
7

Коды исправления ошибок используются в криптографии для решения проблемы согласования информации : Алиса и Боб хотят согласовать ключ K, начиная с (коррелированных) строк X и Y, соответственно. (Примером такой ситуации является протокол, который основан на шумном канале, когда Алиса отправляет X Бобу.) Решение состоит в том, чтобы заставить Алису посылать Бобу некоторую информацию для исправления ошибок C Бобу, чтобы он мог восстановить X. Конечно, проблема в том, что не все так просто: поскольку C передает некоторую информацию злоумышленнику Еве, нам необходимо усилить конфиденциальность, чтобы получить секретный ключ. Это можно сделать с помощью 2-универсальной хеш-функции, что гарантируется оставшейся хеш-леммой.

Совсем недавно, в качестве помехоустойчивого варианта экстракторов были введены нечеткие экстракторы : они извлекают равномерно случайную строку R из своего ввода W, а также выдают «отпечаток» P, такой, что если на входе изменяется какая-то похожая строка W ', случайная строка R может быть восстановлен из P и W '. Конструкция нечетких экстракторов также опирается на коды с исправлением ошибок.

Фелипе Ласерда
источник
6

Энди Друкер уже упоминал опрос Trevisan [Tre04] в комментарии к другому ответу , но я думаю, что его следует упомянуть более крупным шрифтом!

[Tre04] Лука Тревизан. Некоторые приложения теории кодирования в вычислительной сложности. Quaderni di Matematica , 13: 347–424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf

Цуёси Ито
источник
6

Действительно, как упоминала Дана, есть много примеров.

В расчетах на отказоустойчивость коды с исправлением ошибок очень важны. Я думаю, что статья 1988 года Бен-Ор Гольдвассера и Вигдерсона Теоремы о полноте для не криптографических распределенных вычислений с отказоустойчивостью , хотя и без явного цитирования результатов кодов, исправляющих ошибки, имеет тип ECC.

Конечно, «пороговая теорема», допускающая отказоустойчивые квантовые вычисления, в решающей степени опирается на квантовые коды с исправлением ошибок, которые являются квантовыми аналогами обычных ECC.
( Статья в Википедии для пороговой теоремы, безусловно, нуждается в работе; но статья о квантовом исправлении ошибок лучше.)

Gil Kalai
источник
5

Ознакомьтесь со списком документов ECCC, помеченных «кодами, исправляющими ошибки» .

Изучив этот список, вы увидите, что существует связь между кодами, исправляющими ошибки, и PCP (я не знаю, будете ли вы считать это приложением «помимо простого исправления ошибок»), а также обучением PAC .

Джошуа Грохов
источник
2
В частности, коды, известные как «локально проверяемые коды» (LTC), очень похожи на PCP, и идеи, используемые при создании LTC, также были полезны при создании PCP. Кроме того, я не уверен, упоминался ли опрос Тревизана «Некоторые приложения теории кодирования в вычислительной сложности», но это хорошая справка для вашего вопроса.
Энди Друкер
4

Для очень хорошего объяснения того, как коды с исправлением ошибок используются в конкретной практической ситуации, посмотрите на:

Математика компакт-диска, Джек Х. Ван Линт, «Математика везде», М. Эйгнер и Э. Берендс (редакторы), Американское математическое общество, 2010

(Эта книга является переводом с немецкого оригинала.)

Иосиф Малкевич
источник
3

Другое приложение в кодах аутентификации. По сути, это кодировки, предназначенные для обнаружения любых изменений в сообщении и основанные на исправлении ошибок. Это несколько больше, чем простое исправление ошибок, которое влечет за собой предположения о структуре шума.

Джо Фитцсимонс
источник
2

У кода с исправлением ошибок были приложения в тестировании свойств:

(Извините, это немного смещено в сторону статей, которые я написал в соавторстве, в основном из-за моего знакомства с ними.)

Климент С.
источник
1

Мы считаем, что основанная на коде криптография с открытым ключом является постквантовой. На самом деле криптография на основе кода имеет самую длинную историю в истории постквантовых схем с открытыми ключами, но размеры ключей кажутся непрактично большими, как 1 МБ в McBits .

Мы также используем коды с исправлением ошибок в криптографии с открытым ключом на основе решетки, которая использует фазу согласования, как упоминал Фелипе Ласерда. На самом деле, наша лучшая ставка для постквантового обмена ключами - это схема модуля-LWE Кибера (на основе решетки).

Джефф Берджес
источник