Немного предыстории:
Я заинтересован в поиске «менее известных» нижних границ (или результатов твердости) для задачи «Обучение с ошибками» (LWE) и их обобщений, таких как «Обучение с ошибками над кольцами». Для конкретных определений и т. Д., Вот хороший обзор Регева: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf
Стандартный тип (R) предположения в стиле LWE заключается в (возможно, квантовом) сведении к кратчайшей векторной проблеме на (возможно, идеальных) решетках. Известно, что обычная формулировка SVP является NP-трудной, и считается, что ее трудно приблизить к небольшим полиномиальным факторам. (Связанный: Трудно приблизить CVP к / почти полиномиальным / факторам: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) Я также слышал, что упоминалось (с точки зрения квантовых алгоритмов) Аппроксимация некоторых задач решетки (таких как SVP) малыми полиномиальными коэффициентами аппроксимации связана с неабелевой проблемой скрытой подгруппы (которая, как считается, трудна по своим собственным причинам), хотя я никогда не видел явного, формального источника для этого.
Однако меня больше интересуют результаты по твердости (любого типа), возникающие в результате проблемы «Шумный паритет» из теории обучения. Это могут быть результаты твердости класса сложности, конкретные алгоритмические нижние границы, границы сложности выборки или даже нижние границы размера доказательства (например, разрешение). Известно (возможно, очевидно), что LWE можно рассматривать как обобщение проблемы «Шумный паритет / паритет обучения с шумом» (LPN), которая (из Googling), по-видимому, использовалась для снижения твердости в таких областях, как теория кодирования и PAC. учусь.
Посмотрев вокруг себя, я нашел только (слегка субэкспоненциальные) ВЕРХНИЕ СКАЗКИ по проблеме LPN, например, http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf
Вопрос:
Я знаю, что LPN ВЕРНО ЖЕСТКО в образовательном сообществе. Мой вопрос: почему?
Это потому, что все очень старались, но никто еще не нашел хороший алгоритм? Известны ли нижние границы выделенного курсивом сорта выше (или других, которые я пропустил)?
Если ответ будет очень четким, краткое резюме того, что известно и / или ссылки на обзоры / конспекты лекций, было бы здорово.
Если многое неизвестно, чем больше «современных» газет, тем лучше. :) (Спасибо заранее!)